Introduction

Within the subject area of machine learning, gradient descent is perhaps the most well-known and commonly used iterative optimization method for finding the parameters that minimize error functions such as residual sum of squares for (\(L_1\)-regularized) linear regression, or negative log-likelihoods for logistic regression and neural networks.

However, there are a few alternative methods that may perform better than gradient descent in specific cases. For example:

In this notebook, we will be comparing coordinate and gradient descent in the bivariate function setting—functions only accepting two inputs. This comparison is aimed at understanding optimization methods more abstractly, rather than their applications to machine learning.

It is important to note that coordinate descent generally refers to the approach of minimizing a multivariate function by minimizing it in one direction or coordinate at a time (solving univariate optimization problems repeatedly). This means that it is possible to apply coordinate descent to both differentiable and derivative-free contexts3.

However, in this notebook, coordinate descent refers to gradient-based coordinate descent.

Setup

# Set working directory
setwd("~/Development/R/minimizers")

# Install dependencies
#install.packages("shiny")
#install.packages("plotly")
#install.packages("plyr")
#install.packages("ggplot2")
#install.packages("ggpubr")

# Require dependencies
require(shiny)
require(plotly)
require(plyr)
require(ggplot2)
require(ggpubr)

# Set seed for reproducibility
set.seed(9292)

Test functions

Comparison metrics will include benchmarks, number of iterations and convergence/divergence. These metrics will be used to test both optimization methods on two differentiable bivariate functions: the Six-hump camel function and the Peaks function.

Six-hump camel function

The Six-hump camel function is a test function used for investigating the performance of optimization algorithms.4

The function is defined by:

\[ F_1(x,y)=\left(4-2.1x^2+\frac{x^4}{3}\right)x^2+xy+4\left(y^2-1\right)y^2 \] Despite being well defined for all \((x,y)\in\mathbb{R}^2\), the focal point of this function is within the \(x,y\in[-6,6]\) region, where all of the turning points of the function lie. However, for visualization, this region can be made smaller: \(x\in[-2,2],\ y\in[-1,1]\).

# Import Six-hump camel function
source("functions/camel.R")

# Set input variable ranges
F1.x <- seq(-2, 2, length=100)
F1.y <- seq(-1, 1, length=100)
F1.z <- t(outer(F1.x, F1.y, F1))

# Display plot and contours
F1.plot <- plot_ly(x=F1.x, y=F1.y, z=F1.z, width=700, height=500) %>%
  add_surface(contours=list(z=list(show=TRUE, usecolormap=TRUE, highlightcolor="#ff0000", project=list(z=TRUE)))) %>%
  layout(scene=list(zaxis=list(range=c(-2,6)), aspectmode="manual", aspectratio=list(x=1, y=1, z=0.6)),
         title="Six-hump camel function (F1)")

div(F1.plot, align="center")

Minima

Type \(x\) \(y\) \(f(x,y)\)
Global \(0.089842\) \(-0.712656\) \(-1.031628453\)
Global \(-0.089842\) \(0.712656\) \(-1.031628453\)

Partial derivatives

The gradient vector \(\nabla F_1(x,y)\) for the Six-hump camel function consists of the following partial derivatives:

\[ \begin{align} \nabla F_1(x,y) &=\begin{pmatrix} \frac{\partial F_1}{\partial x}\\ \frac{\partial F_1}{\partial y} \end{pmatrix}\\ &=\begin{pmatrix} 2\left(x^5-4.2x^3+4x+0.5y\right) \\ x+16y^3-8y \end{pmatrix} \end{align} \]

The Peaks function

The Peaks function5 is a function often used to demonstrate 3D graphing software or libraries in MATLAB and other programming languages.

The function is defined by:

\[ \begin{align} F_2(x,y)&= 3(1-x)^2e^{-x^2-(y+1)^2}\\ &+10\left(\frac{1}{5}x-x^3-y^5\right)e^{-\left(x^2+y^2\right)}\\ &+\frac{1}{3}e^{-(x+1)^2-y^2} \end{align} \]

For optimization tests, this function is normally restricted to the \(x,y\in[-4,4]\) region, as this is where the extrema of the function lie. However, for visualization purposes, \([-3,3]\) is preferable for \(x\).

# Import Peaks function
source("functions/peaks.R")

# Set input variable ranges
F2.x <- seq(-3, 3, length=100)
F2.y <- seq(-3, 3, length=100)
F2.z <- t(outer(F2.x, F2.y, F2))

# Display plot and contours
F2.plot <- plot_ly(x=F2.x, y=F2.y, z=F2.z, width=700, height=500) %>%
  add_surface(contours=list(z=list(show=TRUE, usecolormap=TRUE, highlightcolor="#ff0000", project=list(z=TRUE)))) %>%
  layout(scene=list(aspectmode="manual", aspectratio=list(x=1, y=1, z=0.65)),
         title="Peaks function (F2)")

div(F2.plot, align="center")

Minima

Type \(x\) \(y\) \(f(x,y)\)
Global \(0.2282799999\) \(-1.6255310720\) \(-6.5511333326\)

Partial derivatives

The gradient vector \(\nabla F_2(x,y)\) for the Peaks function consists of the following partial derivatives:

\[ \begin{align} \nabla F_2(x,y) &=\begin{pmatrix} \frac{\partial F_2}{\partial x}\\ \frac{\partial F_2}{\partial y} \end{pmatrix}\\ &=\begin{pmatrix} -\frac{2}{3}e^{-\big(x^2 + 2 x + (y + 1)^2\big)} \Big( e^{2x+2y+1}\big( 30x^3-6x^2+30x(y^5-1)+3 \big) + 9e^{2x}\left( x^3-2x^2+1 \right) + (x+1)\left(-e^{2y}\right) \Big)\\ -\frac{2}{3}e^{-\big(x^2+2x+(y+1)^2\big)} \Big( 3ye^{2x+2y+1}\big( 10x^2-2x+5(2y^2-5)y^3 \big) + 9e^{2x}(1-x)^2(y+1) - ye^{2y} \Big) \end{pmatrix} \end{align} \]

These partial derivatives are far more complex than those of the Six-hump camel function. Since both of the optimization methods we are testing are gradient-based, it is likely that benchmarks for this test function will take significantly longer.

With complex derivatives such as these (or when the function is non-differentiable entirely), it is often more preferable to use derivative-free optimization methods6 such as the Nelder-Mead method7.

Optimization methods

Gradient descent

Gradient descent is a gradient-based iterative optimization method. Gradient descent works by iteratively updating the current position by taking a small step in the direction of steepest descent8.

\[ \mathbf{x}_{i+1} \leftarrow \mathbf{x}_i - \eta \nabla F(\mathbf{x}) \]

Where:

  • \(\eta\) is the learning rate for the algorithm—the size of the step taken on each iteration.
  • \(\nabla F(\mathbf{x})\) is the gradient vector of \(F(\mathbf{x})\), which represents the direction of steepest ascent.

With a bivariate function \(F(x,y)\), we can update the vector \(\begin{pmatrix}x \\ y\end{pmatrix}\) with:

\[ \begin{pmatrix} x \\ y \end{pmatrix} \leftarrow \begin{pmatrix} x \\ y \end{pmatrix} -\eta\begin{pmatrix} \frac{\partial F}{\partial x} \\ \frac{\partial F}{\partial y} \end{pmatrix} \] Choosing the learning rate \(\eta\) is a frequent problem in optimization—too large of a learning rate sometimes leads to divergence and missing the minimum due to having such large steps. Conversely, a very small learning rate will require many iterations to converge, which can be costly in terms of time and CPU/memory usage.

In order to ensure convergence, we will use a small learning rate.

# Set a small learning rate
rate <- 0.05

It is also necessary to set a maximum number of iterations for iterative methods. In the event that the method diverges, it will still terminate execution. Likewise, if \(\eta\) is too small and too many iterations have passed without reaching a minimum, the method will stop.

In this case, the maximum number of iterations will be \(200\).

# Set maximum number of iterations
max_iterations <- 200

In this notebook, we will say that an optimization method converges to a minimum point \(\begin{pmatrix}x^* \\ y^*\end{pmatrix}\) if it reaches a point \(\begin{pmatrix}x \\ y\end{pmatrix}\) such that the Euclidean distance (\(L_2\) norm) between the two is less than some \(\epsilon\in\mathbb{R^+}\). In other words, if \(\begin{pmatrix}x \\ y\end{pmatrix}\) is in the \(\epsilon\)-neighbourhood of \(\begin{pmatrix}x^* \\ y^*\end{pmatrix}\): \[ \left|\left| \begin{pmatrix}x^* \\ y^*\end{pmatrix} - \begin{pmatrix}x \\ y\end{pmatrix} \right|\right|_2 < \epsilon\\ \]

# Set a small epsilon
epsilon <- 0.05

We define the gradient descent algorithm iteratively as:

# Gradient descent
#
# Parameters:
#   x.initial: The starting x-coordinate
#   y.initial: The starting y-coordinate
#   FUN: The gradient vector for the function being optimized
#   minimum: The actual minimum of the function
#
# Returns:
#   A tuple consisting of (termination reason, iterations).
#
gradient.descent <- function(x.initial, y.initial, FUN, minimum) {
  for (iterations in 1:max_iterations) {
    # Add starting point to path if it is the first iteration
    if(iterations == 1) path[[1]] <<- c(x.initial, y.initial)
    
    # Retrieve current position from path vector
    x.i = path[[iterations]][1]
    y.i = path[[iterations]][2]
    
    # Check for convergence
    if(dist(rbind(c(x.i, y.i), minimum)) <= epsilon) return(c("Converged", iterations-1))
    
    # Make an update to the current position
    updated <- c(x.i, y.i) - rate * FUN(x.i, y.i)
    
    # Increment iterations and store updated position in `path` variable
    iterations <- iterations + 1
    path[[iterations]] <<- updated
  }
  
  return(c("Maximum iterations reached", iterations-1))
}

Where: path is a global variable that stores all of the intermediate vectors during the optimization process.

Testing on the Six-hump camel function

Before we start testing, we need a minimum of interest, along with a starting point for the optimization process:

# Minimum of interest
F1.minimum <- c(0.089842, -0.712656)

# Starting point
F1.start <- c(0.85, 0)

Additionally, we will need to initialize the path variable for keeping track of the updated vectors during the optimization process. This variable will be reused for other tests, so we will also define a reset function.

# Create an empty path vector
path <<- vector('list', max_iterations)
Error in names(x) <- paste("V", seq_along(x), sep = "") : 
  'names' attribute [1] must be the same length as the vector [0]
# Reset function for the `path` variable
reset_path <- function() { path <<- vector('list', max_iterations) }

Running the gradient descent method (with benchmarking):

# Run timed gradient descent
F1.gradient.time <- proc.time()
F1.gradient.results <- gradient.descent(F1.start[1], F1.start[2], F1.d, F1.minimum)
F1.gradient.time <- proc.time() - F1.gradient.time

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F1.gradient.contour <- plot_ly(x=~F1.x, y=~F1.y, z=F1.z, width=800, height=500,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F1.minimum[1], y=F1.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F1.start[1], y=F1.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=30, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F1.minimum[1], y=F1.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="GD optimization of the six-hump camel function (F1)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F1.gradient.contour, align="center")

Termination reason and number of iterations:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F1.gradient.results[1], F1.gradient.results[2]))
Termination reason: Converged
Number of iterations: 9

Benchmarking for these optimization methods will be done with the proc.time base function in R9. This function records the time taken for a specific action to finish execution, according three different time measures:

  1. user: The CPU time charged for the execution of user instructions of the calling process.
  2. system: The CPU time charged for execution by the system on behalf of the calling process.
  3. elapsed: The “real” elapsed time since the process was started.

Printing the proc_time result displays these measures in order:

print(F1.gradient.time)
   user  system elapsed 
  0.198   0.084   0.293

Testing on the Peaks function

Setting a minimum of interest, along with a starting point:

# Minimum of interest
F2.minimum <- c(0.228279999979237, -1.625531071954464)

# Starting point
F2.start <- c(1, -0.2)

Resetting the optimization path variable (path) and running the gradient descent method (with benchmarking):

# Resetting optimization path
reset_path()
Error in names(x) <- paste("V", seq_along(x), sep = "") : 
  'names' attribute [1] must be the same length as the vector [0]
# Run timed gradient descent
F2.gradient.time <- proc.time()
F2.gradient.results <- gradient.descent(F2.start[1], F2.start[2], F2.d, F2.minimum)
F2.gradient.time <- proc.time() - F2.gradient.time

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F2.gradient.contour <- plot_ly(x=~F2.x, y=~F2.y, z=F2.z, width=700, height=600,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F2.minimum[1], y=F2.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F2.start[1], y=F2.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-5, ay=-40,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F2.minimum[1], y=F2.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="GD optimization of the peaks function (F2)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F2.gradient.contour, align="center")

Termination reason and number of iterations:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F2.gradient.results[1], F2.gradient.results[2]))
Termination reason: Converged
Number of iterations: 8

Benchmarks:

print(F2.gradient.time)
   user  system elapsed 
  0.130   0.004   0.140

Coordinate descent

Gradient-based coordinate descent is a similar method of optimization to gradient descent, as each iteration still updates the position by moving (by a step size \(\eta\)) in the direction of steepest descent.

However, the main difference with coordinate descent is that we optimize one coordinate at a time—essentially solving \(d\) univariate optimization problems (if the function \(F\) is \(d\)-variate). The optimization paths from these sub-problems are then combined to form a solution to the original optimization problem.

For a single coordinate \(i\), the iterative update formula is given by: \[ x_{i+1} \leftarrow x_i - \eta \frac{\partial}{\partial x_i}F(\mathbf{x}) \]

We define the coordinate descent algorithm iteratively as:

# Coordinate descent
#
# Parameters:
#   x.initial: The starting x-coordinate
#   y.initial: The starting y-coordinate
#   FUN: The gradient vector for the function being optimized
#   minimum: The actual minimum of the function
#
# Returns:
#   A tuple consisting of (termination reason, iterations).
#
coordinate.descent <- function(x.initial, y.initial, FUN, minimum) {
  for (iterations in 1:max_iterations) {
    # Add starting point to path if it is the first iteration
    if(iterations == 1) path[[1]] <<- c(x.initial, y.initial)
    
    # Retrieve current position from path vector
    x.i = path[[iterations]][1]
    y.i = path[[iterations]][2]
    
    # Check for convergence
    if(dist(rbind(c(x.i, y.i), minimum)) <= epsilon) return(c("Converged", iterations-1))
    
    # Make an update to the current position
    updated <- NULL
    if((iterations %% 2) == 1) {
      updated <- c(x.i, y.i) - rate * c(FUN(x.i, y.i)[1], 0)
    } else {
      updated <- c(x.i, y.i) - rate * c(0, FUN(x.i, y.i)[2])
    }
    
    # Increment iterations and store updated position in `path` variable
    iterations <- iterations + 1
    path[[iterations]] <<- updated
  }
  
  return(c("Maximum iterations reached", iterations-1))
}

Testing on the Six-hump camel function

Running the coordinate descent method (with benchmarking):

# Reset optimization path
reset_path()
Error in names(x) <- paste("V", seq_along(x), sep = "") : 
  'names' attribute [1] must be the same length as the vector [0]
# Run timed coordinate descent
F1.coordinate.time <- proc.time()
F1.coordinate.results <- coordinate.descent(F1.start[1], F1.start[2], F1.d, F1.minimum)
F1.coordinate.time <- proc.time() - F1.coordinate.time

# Retrieve number of iterations
F1.coordinate.iterations <- as.numeric(F1.coordinate.results[[2]])

Termination reason and number of iterations for coordinate descent optimization:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F1.coordinate.results[1], F1.coordinate.results[2]))
Termination reason: Converged
Number of iterations: 18

Benchmarks for coordinate descent optimization:

print(F1.coordinate.time)
   user  system elapsed 
  0.064   0.002   0.067

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F1.coordinate.contour <- plot_ly(x=~F1.x, y=~F1.y, z=F1.z, width=800, height=500,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F1.minimum[1], y=F1.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F1.start[1], y=F1.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=30, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F1.minimum[1], y=F1.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="CD optimization of the six-hump camel function (F1)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F1.coordinate.contour, align="center")

Testing on the Peaks function

Running the coordinate descent method (with benchmarking):

# Reset optimization path
reset_path()
Error in names(x) <- paste("V", seq_along(x), sep = "") : 
  'names' attribute [1] must be the same length as the vector [0]
# Run timed x-coordinate descent
F2.coordinate.time <- proc.time()
F2.coordinate.results <- coordinate.descent(F2.start[1], F2.start[2], F2.d, F2.minimum)
F2.coordinate.time <- proc.time() - F2.coordinate.time

# Trucate NULLs in optimization path list
F2.coordinate.path <- Filter(Negate(is.null), path)

# Retrieve number of iterations
F2.coordinate.iterations <- as.numeric(F2.coordinate.results[[2]])

Termination reason and number of iterations for coordinate descent optimization:

cat(sprintf("Termination reason: %s\nNumber of iterations: %s", F2.coordinate.results[1], F2.coordinate.results[2]))
Termination reason: Converged
Number of iterations: 18

Benchmarks for coordinate descent optimization:

print(F2.coordinate.time)
   user  system elapsed 
  0.045   0.002   0.047

Plotting the contour and path of updates:

# Convert the `path` variable to a matrix
path <- matrix(unlist(path), ncol=2, byrow=TRUE)

# Display contour and optimization path
F2.coordinate.contour <- plot_ly(x=~F2.x, y=~F2.y, z=F2.z, width=700, height=600,
                      type="contour", contours=list(showlabels = TRUE)) %>%

  # Add optimization path trace
  add_trace(x=path[,1], y=path[,2], type="scatter", name="Optimization path", mode="line") %>%

  # Add cross at target minimum position
  add_trace(x=F2.minimum[1], y=F2.minimum[2], type="scatter", name="Target minimum",
            mode="markers", marker=list(color="#5ec4a7", size=6, symbol="x")) %>%

  # Add arrow and annotation for starting position
  add_annotations(x=F2.start[1], y=F2.start[2], text="Start",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=30, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Add arrow and annotation for target minimum
  add_annotations(x=F2.minimum[1], y=F2.minimum[2], text="Target\nminimum",
                  showarrow=TRUE, arrowhead=4, arrowsize=.5, arrowcolor='white', ax=-80, ay=-30,
                  font=list(color = '#81ccc2', family='helvetica', size = 14)) %>%

  # Adding and positioning plot title
  layout(title="CD optimization of the peaks function (F2)", margin=list(l=125, r=0, t=60, b=60))

# Display the contour plot
div(F2.coordinate.contour, align="center")

Method comparison metrics

Benchmarks

Preparing the benchmark comparison plot:

# Dataframe representing the gradient and coordinate descent benchmarks on F1
F1.benchmarks.df <- data.frame(
  Method=rep(c("Gradient descent", "Coordinate descent"), each=3),
  Type=c("User", "System", "Elapsed (Total)"),
  Time=round(c(F1.gradient.time[1:3], F1.coordinate.time[1:3]), digits=3)
)

# Grouped bar plot for comparison of the benchmarks
F1.benchmarks.plot <- ggplot(data=F1.benchmarks.df, aes(x=Type, y=Time, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  geom_text(aes(label=Time), hjust=0.5, color="black", size=2.5, position = position_dodge(0.9), size=3.5) +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  theme_minimal() +
  ggtitle("F1 (six-hump camel function)") +
  theme(plot.margin=unit(c(0.5, 0, 0, 0), "cm")) +
  coord_flip()

# Dataframe representing the gradient and coordinate descent benchmarks on F2
F2.benchmarks.df <- data.frame(
  Method=rep(c("Gradient descent", "Coordinate descent"), each=3),
  Type=c("User", "System", "Elapsed (Total)"),
  Time=round(c(F2.gradient.time[1:3], F2.coordinate.time[1:3]), digits=3)
)

# Grouped bar plot for comparison of the benchmarks
F2.benchmarks.plot <- ggplot(data=F2.benchmarks.df, aes(x=Type, y=Time, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  geom_text(aes(label=Time), hjust=0.5, color="black", size=2.5, position = position_dodge(0.9), size=3.5) +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  theme_minimal() +
  ggtitle("F2 (peaks function)") +
  coord_flip()

# Arranging the subplots
benchmarks.plot <- ggarrange(F1.benchmarks.plot, F2.benchmarks.plot, nrow=2, common.legend=TRUE, legend="bottom")

Plotting the benchmarks comparison:

# Add a plot title
annotate_figure(benchmarks.plot, 
                top=text_grob("Gradient and coordinate descent benchmarks", size=16, face="bold"))

As explained earlier, coordinate descent tends to optimize faster (in terms of run-time) than gradient descent. Despite this, we cannot definitely assume that coordinate descent will always be faster without performing repeated experiments or trying other functions and combinations of \(\eta\), \(\epsilon\) and starting position.

Number of iterations

Preparing the iteration comparison plot:

# Dataframe representing the gradient and coordinate descent iterations on F1
F1.iterations.df <- data.frame(
  Method=c("Gradient descent", "Coordinate descent"),
  Iterations=round(as.numeric(c(F1.gradient.results[[2]], F1.coordinate.iterations)))
)

# Bar plot for comparison of iterations
F1.iterations.plot <- ggplot(data=F1.iterations.df, aes(x=Method, y=Iterations, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  geom_text(aes(label=Iterations), hjust=3, color="white", size=4, position = position_dodge(0.9), size=3.5) +
  scale_y_continuous(breaks=function(x) unique(floor(pretty(seq(0, (max(x) + 1) * 1.1))))) + 
  theme_minimal() +
  theme(axis.text.y = element_blank(), axis.ticks.y = element_blank()) +
  ggtitle("F1 (six-hump camel function)") +
  theme(plot.margin=unit(c(0.5, 0, 0, 0), "cm")) +
  coord_flip()

# Dataframe representing the gradient and coordinate descent iterations on F2
F2.iterations.df <- data.frame(
  Method=c("Gradient descent", "Coordinate descent"),
  Iterations=round(as.numeric(c(F2.gradient.results[[2]], F2.coordinate.iterations)))
)

# Bar plot for comparison of iterations
F2.iterations.plot <- ggplot(data=F2.iterations.df, aes(x=Method, y=Iterations, fill=Method)) +
  geom_bar(stat="identity", position="dodge") +
  scale_fill_manual("Method", values=c("Gradient descent"="#70bacf", "Coordinate descent"="#eb6963")) +
  #scale_fill_brewer(palette="Paired") +
  geom_text(aes(label=Iterations), hjust=3, color="white", size=4, position = position_dodge(0.9), size=3.5) +
  scale_y_continuous(breaks=function(x) unique(floor(pretty(seq(0, (max(x) + 1) * 1.1))))) + 
  theme_minimal() +
  theme(axis.text.y = element_blank(), axis.ticks.y = element_blank()) +
  ggtitle("F2 (peaks function)") +
  coord_flip()

# Arranging the subplots
iterations.plot <- ggarrange(F1.iterations.plot, F2.iterations.plot, nrow=2, common.legend=TRUE, legend="bottom")

Plotting the iterations comparison:

# Add a plot title
annotate_figure(iterations.plot, 
                top=text_grob("Gradient and coordinate descent iterations", size=16, face="bold"))

Unlike benchmarks, the number of iterations that each of these optimization method takes to converge (if it does converge) does not vary per experiment—it will never change unless we change \(\eta\), \(\epsilon\) or the starting position, which we didn’t. For this reason, repeated experiments are not as necessary as they are for benchmarking, where the uncertainty of CPU resource allocation etc. is enough to warrant repeated experiments.

However, it still isn’t fair to make a concrete conclusion from these results, since we would need to test the optimization methods on different objective functions, different \(\eta\), \(\epsilon\) and starting positions.

Nevertheless, coordinate descent optimized the objective functions in far more iterations than gradient descent.

Resources

  1. https://en.wikipedia.org/wiki/Limited-memory_BFGS↩

  2. https://web.stanford.edu/~hastie/TALKS/glmnet.pdf↩

  3. https://en.wikipedia.org/wiki/Coordinate_descent↩

  4. https://www.sfu.ca/~ssurjano/camel6.html↩

  5. https://al-roomi.org/benchmarks/unconstrained/2-dimensions/63-peaks-function↩

  6. https://en.wikipedia.org/wiki/Derivative-free_optimization↩

  7. https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method↩

  8. https://ml-cheatsheet.readthedocs.io/en/latest/gradient_descent.html↩

  9. https://stat.ethz.ch/R-manual/R-devel/library/base/html/proc.time.html↩

LS0tCnRpdGxlOiBDb21wYXJpc29uIG9mIGdyYWRpZW50LWJhc2VkIGNvb3JkaW5hdGUgZGVzY2VudCBhbmQgZ3JhZGllbnQgZGVzY2VudCBvbiBjb250aW51b3VzIGJpdmFyaWF0ZSBmdW5jdGlvbnMKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICBjb2RlX2ZvbGRpbmc6IG5vbmUKICAgIHRoZW1lOiBzcGFjZWxhYgogICAgdG9jOiB5ZXMKLS0tCgojIEludHJvZHVjdGlvbgoKV2l0aGluIHRoZSBzdWJqZWN0IGFyZWEgb2YgbWFjaGluZSBsZWFybmluZywgZ3JhZGllbnQgZGVzY2VudCBpcyBwZXJoYXBzIHRoZSBtb3N0IHdlbGwta25vd24gYW5kIGNvbW1vbmx5IHVzZWQgaXRlcmF0aXZlIG9wdGltaXphdGlvbiBtZXRob2QgZm9yIGZpbmRpbmcgdGhlIHBhcmFtZXRlcnMgdGhhdCBtaW5pbWl6ZSBlcnJvciBmdW5jdGlvbnMgc3VjaCBhcyByZXNpZHVhbCBzdW0gb2Ygc3F1YXJlcyBmb3IgKCRMXzEkLXJlZ3VsYXJpemVkKSBsaW5lYXIgcmVncmVzc2lvbiwgb3IgbmVnYXRpdmUgbG9nLWxpa2VsaWhvb2RzIGZvciBsb2dpc3RpYyByZWdyZXNzaW9uIGFuZCBuZXVyYWwgbmV0d29ya3MuCgpIb3dldmVyLCB0aGVyZSBhcmUgYSBmZXcgYWx0ZXJuYXRpdmUgbWV0aG9kcyB0aGF0IG1heSBwZXJmb3JtIGJldHRlciB0aGFuIGdyYWRpZW50IGRlc2NlbnQgaW4gc3BlY2lmaWMgY2FzZXMuIEZvciBleGFtcGxlOgoKLSAqKkxpbWl0ZWQtbWVtb3J5IEJGR1MgKEwtQkZHUykqKiBpcyBwYXJ0aWN1bGFybHkgc3VpdGVkIHRvIHByb2JsZW1zIHdpdGggdmVyeSBsYXJnZSBudW1iZXJzIG9mIHZhcmlhYmxlc1tebC1iZmdzXS4KLSAqKkNvb3JkaW5hdGUgZGVzY2VudCoqIGlzIGdlbmVyYWxseSBmYXN0ZXIgdGhhbiBncmFkaWVudCBkZXNjZW50IChkZXNwaXRlIGNvbnZlcmdpbmcgaW4gbW9yZSBpdGVyYXRpb25zKSwgYW5kIGlzIGZyZXF1ZW50bHkgdXNlZCBmb3IgJExfMSQtcmVndWxhcml6ZWQgbGVhc3Qgc3F1YXJlcyBwcm9ibGVtc1teZ2xtbmV0XS4KCi0tLQoKSW4gdGhpcyBub3RlYm9vaywgd2Ugd2lsbCBiZSBjb21wYXJpbmcgY29vcmRpbmF0ZSBhbmQgZ3JhZGllbnQgZGVzY2VudCBpbiB0aGUgYml2YXJpYXRlIGZ1bmN0aW9uIHNldHRpbmctLS1mdW5jdGlvbnMgb25seSBhY2NlcHRpbmcgdHdvIGlucHV0cy4gVGhpcyBjb21wYXJpc29uIGlzIGFpbWVkIGF0IHVuZGVyc3RhbmRpbmcgb3B0aW1pemF0aW9uIG1ldGhvZHMgbW9yZSBhYnN0cmFjdGx5LCByYXRoZXIgdGhhbiB0aGVpciBhcHBsaWNhdGlvbnMgdG8gbWFjaGluZSBsZWFybmluZy4KCkl0IGlzIGltcG9ydGFudCB0byBub3RlIHRoYXQgY29vcmRpbmF0ZSBkZXNjZW50IGdlbmVyYWxseSByZWZlcnMgdG8gdGhlIGFwcHJvYWNoIG9mIG1pbmltaXppbmcgYSBtdWx0aXZhcmlhdGUgZnVuY3Rpb24gYnkgbWluaW1pemluZyBpdCBpbiBvbmUgZGlyZWN0aW9uIG9yIGNvb3JkaW5hdGUgYXQgYSB0aW1lIChzb2x2aW5nIHVuaXZhcmlhdGUgb3B0aW1pemF0aW9uIHByb2JsZW1zIHJlcGVhdGVkbHkpLiBUaGlzIG1lYW5zIHRoYXQgaXQgaXMgcG9zc2libGUgdG8gYXBwbHkgY29vcmRpbmF0ZSBkZXNjZW50IHRvIGJvdGggZGlmZmVyZW50aWFibGUgYW5kIGRlcml2YXRpdmUtZnJlZSBjb250ZXh0c1teY29vcmRpbmF0ZS1kZXNjZW50XS4KCkhvd2V2ZXIsIGluIHRoaXMgbm90ZWJvb2ssIGNvb3JkaW5hdGUgZGVzY2VudCByZWZlcnMgdG8gZ3JhZGllbnQtYmFzZWQgY29vcmRpbmF0ZSBkZXNjZW50LgoKIyMgU2V0dXAKCmBgYHtyfQojIFNldCB3b3JraW5nIGRpcmVjdG9yeQpzZXR3ZCgifi9EZXZlbG9wbWVudC9SL21pbmltaXplcnMiKQoKIyBJbnN0YWxsIGRlcGVuZGVuY2llcwojaW5zdGFsbC5wYWNrYWdlcygic2hpbnkiKQojaW5zdGFsbC5wYWNrYWdlcygicGxvdGx5IikKI2luc3RhbGwucGFja2FnZXMoInBseXIiKQojaW5zdGFsbC5wYWNrYWdlcygiZ2dwbG90MiIpCiNpbnN0YWxsLnBhY2thZ2VzKCJnZ3B1YnIiKQoKIyBSZXF1aXJlIGRlcGVuZGVuY2llcwpyZXF1aXJlKHNoaW55KQpyZXF1aXJlKHBsb3RseSkKcmVxdWlyZShwbHlyKQpyZXF1aXJlKGdncGxvdDIpCnJlcXVpcmUoZ2dwdWJyKQoKIyBTZXQgc2VlZCBmb3IgcmVwcm9kdWNpYmlsaXR5CnNldC5zZWVkKDkyOTIpCmBgYAoKIyMgVGVzdCBmdW5jdGlvbnMKCkNvbXBhcmlzb24gbWV0cmljcyB3aWxsIGluY2x1ZGUgYmVuY2htYXJrcywgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgYW5kIGNvbnZlcmdlbmNlL2RpdmVyZ2VuY2UuIFRoZXNlIG1ldHJpY3Mgd2lsbCBiZSB1c2VkIHRvIHRlc3QgYm90aCBvcHRpbWl6YXRpb24gbWV0aG9kcyBvbiB0d28gZGlmZmVyZW50aWFibGUgYml2YXJpYXRlIGZ1bmN0aW9uczogdGhlICoqU2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24qKiBhbmQgdGhlICoqUGVha3MgZnVuY3Rpb24qKi4KCiMjIyBTaXgtaHVtcCBjYW1lbCBmdW5jdGlvbgoKVGhlIFNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uIGlzIGEgdGVzdCBmdW5jdGlvbiB1c2VkIGZvciBpbnZlc3RpZ2F0aW5nIHRoZSBwZXJmb3JtYW5jZSBvZiBvcHRpbWl6YXRpb24gYWxnb3JpdGhtcy5bXmNhbWVsXQoKVGhlIGZ1bmN0aW9uIGlzIGRlZmluZWQgYnk6CgokJApGXzEoeCx5KT1cbGVmdCg0LTIuMXheMitcZnJhY3t4XjR9ezN9XHJpZ2h0KXheMit4eSs0XGxlZnQoeV4yLTFccmlnaHQpeV4yCiQkCkRlc3BpdGUgYmVpbmcgd2VsbCBkZWZpbmVkIGZvciBhbGwgJCh4LHkpXGluXG1hdGhiYntSfV4yJCwgdGhlIGZvY2FsIHBvaW50IG9mIHRoaXMgZnVuY3Rpb24gaXMgd2l0aGluIHRoZSAkeCx5XGluWy02LDZdJCByZWdpb24sIHdoZXJlIGFsbCBvZiB0aGUgdHVybmluZyBwb2ludHMgb2YgdGhlIGZ1bmN0aW9uIGxpZS4gSG93ZXZlciwgZm9yIHZpc3VhbGl6YXRpb24sIHRoaXMgcmVnaW9uIGNhbiBiZSBtYWRlIHNtYWxsZXI6ICR4XGluWy0yLDJdLFwgeVxpblstMSwxXSQuCgpgYGB7cn0KIyBJbXBvcnQgU2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24Kc291cmNlKCJmdW5jdGlvbnMvY2FtZWwuUiIpCgojIFNldCBpbnB1dCB2YXJpYWJsZSByYW5nZXMKRjEueCA8LSBzZXEoLTIsIDIsIGxlbmd0aD0xMDApCkYxLnkgPC0gc2VxKC0xLCAxLCBsZW5ndGg9MTAwKQpGMS56IDwtIHQob3V0ZXIoRjEueCwgRjEueSwgRjEpKQoKIyBEaXNwbGF5IHBsb3QgYW5kIGNvbnRvdXJzCkYxLnBsb3QgPC0gcGxvdF9seSh4PUYxLngsIHk9RjEueSwgej1GMS56LCB3aWR0aD03MDAsIGhlaWdodD01MDApICU+JQogIGFkZF9zdXJmYWNlKGNvbnRvdXJzPWxpc3Qoej1saXN0KHNob3c9VFJVRSwgdXNlY29sb3JtYXA9VFJVRSwgaGlnaGxpZ2h0Y29sb3I9IiNmZjAwMDAiLCBwcm9qZWN0PWxpc3Qoej1UUlVFKSkpKSAlPiUKICBsYXlvdXQoc2NlbmU9bGlzdCh6YXhpcz1saXN0KHJhbmdlPWMoLTIsNikpLCBhc3BlY3Rtb2RlPSJtYW51YWwiLCBhc3BlY3RyYXRpbz1saXN0KHg9MSwgeT0xLCB6PTAuNikpLAogICAgICAgICB0aXRsZT0iU2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24gKEYxKSIpCgpkaXYoRjEucGxvdCwgYWxpZ249ImNlbnRlciIpCmBgYAoKIyMjIyBNaW5pbWEKCnwgVHlwZSB8ICR4JCB8ICR5JCB8ICRmKHgseSkkIHwKfC0tLS0tLXwtLS0tLXwtLS0tLXwtLS0tLS0tLS0tfAp8R2xvYmFsfCQwLjA4OTg0MiR8JC0wLjcxMjY1NiR8JC0xLjAzMTYyODQ1MyR8CnxHbG9iYWx8JC0wLjA4OTg0MiR8JDAuNzEyNjU2JHwkLTEuMDMxNjI4NDUzJHwKCiMjIyMgUGFydGlhbCBkZXJpdmF0aXZlcwoKVGhlIGdyYWRpZW50IHZlY3RvciAkXG5hYmxhIEZfMSh4LHkpJCBmb3IgdGhlIFNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uIGNvbnNpc3RzIG9mIHRoZSBmb2xsb3dpbmcgcGFydGlhbCBkZXJpdmF0aXZlczoKCiQkClxiZWdpbnthbGlnbn0KICBcbmFibGEgRl8xKHgseSkKICAmPVxiZWdpbntwbWF0cml4fQogICAgXGZyYWN7XHBhcnRpYWwgRl8xfXtccGFydGlhbCB4fVxcCiAgICBcZnJhY3tccGFydGlhbCBGXzF9e1xwYXJ0aWFsIHl9CiAgXGVuZHtwbWF0cml4fVxcCiAgJj1cYmVnaW57cG1hdHJpeH0KICAgIDJcbGVmdCh4XjUtNC4yeF4zKzR4KzAuNXlccmlnaHQpCiAgICBcXAogICAgeCsxNnleMy04eQogIFxlbmR7cG1hdHJpeH0KXGVuZHthbGlnbn0KJCQKCiMjIyBUaGUgUGVha3MgZnVuY3Rpb24KClRoZSBQZWFrcyBmdW5jdGlvbltecGVha3NdIGlzIGEgZnVuY3Rpb24gb2Z0ZW4gdXNlZCB0byBkZW1vbnN0cmF0ZSAzRCBncmFwaGluZyBzb2Z0d2FyZSBvciBsaWJyYXJpZXMgaW4gTUFUTEFCIGFuZCBvdGhlciBwcm9ncmFtbWluZyBsYW5ndWFnZXMuCgpUaGUgZnVuY3Rpb24gaXMgZGVmaW5lZCBieToKCiQkClxiZWdpbnthbGlnbn0KICBGXzIoeCx5KSY9CiAgMygxLXgpXjJlXnsteF4yLSh5KzEpXjJ9XFwKICAmKzEwXGxlZnQoXGZyYWN7MX17NX14LXheMy15XjVccmlnaHQpZV57LVxsZWZ0KHheMit5XjJccmlnaHQpfVxcCiAgJitcZnJhY3sxfXszfWVeey0oeCsxKV4yLXleMn0KXGVuZHthbGlnbn0KJCQKCkZvciBvcHRpbWl6YXRpb24gdGVzdHMsIHRoaXMgZnVuY3Rpb24gaXMgbm9ybWFsbHkgcmVzdHJpY3RlZCB0byB0aGUgJHgseVxpblstNCw0XSQgcmVnaW9uLCBhcyB0aGlzIGlzIHdoZXJlIHRoZSBleHRyZW1hIG9mIHRoZSBmdW5jdGlvbiBsaWUuIEhvd2V2ZXIsIGZvciB2aXN1YWxpemF0aW9uIHB1cnBvc2VzLCAkWy0zLDNdJCBpcyBwcmVmZXJhYmxlIGZvciAkeCQuCgpgYGB7cn0KIyBJbXBvcnQgUGVha3MgZnVuY3Rpb24Kc291cmNlKCJmdW5jdGlvbnMvcGVha3MuUiIpCgojIFNldCBpbnB1dCB2YXJpYWJsZSByYW5nZXMKRjIueCA8LSBzZXEoLTMsIDMsIGxlbmd0aD0xMDApCkYyLnkgPC0gc2VxKC0zLCAzLCBsZW5ndGg9MTAwKQpGMi56IDwtIHQob3V0ZXIoRjIueCwgRjIueSwgRjIpKQoKIyBEaXNwbGF5IHBsb3QgYW5kIGNvbnRvdXJzCkYyLnBsb3QgPC0gcGxvdF9seSh4PUYyLngsIHk9RjIueSwgej1GMi56LCB3aWR0aD03MDAsIGhlaWdodD01MDApICU+JQogIGFkZF9zdXJmYWNlKGNvbnRvdXJzPWxpc3Qoej1saXN0KHNob3c9VFJVRSwgdXNlY29sb3JtYXA9VFJVRSwgaGlnaGxpZ2h0Y29sb3I9IiNmZjAwMDAiLCBwcm9qZWN0PWxpc3Qoej1UUlVFKSkpKSAlPiUKICBsYXlvdXQoc2NlbmU9bGlzdChhc3BlY3Rtb2RlPSJtYW51YWwiLCBhc3BlY3RyYXRpbz1saXN0KHg9MSwgeT0xLCB6PTAuNjUpKSwKICAgICAgICAgdGl0bGU9IlBlYWtzIGZ1bmN0aW9uIChGMikiKQoKZGl2KEYyLnBsb3QsIGFsaWduPSJjZW50ZXIiKQpgYGAKCiMjIyMgTWluaW1hCgp8IFR5cGUgfCAkeCQgfCAkeSQgfCAkZih4LHkpJCB8CnwtLS0tLS18LS0tLS18LS0tLS18LS0tLS0tLS0tLXwKfEdsb2JhbHwkMC4yMjgyNzk5OTk5JHwkLTEuNjI1NTMxMDcyMCR8JC02LjU1MTEzMzMzMjYkfAoKIyMjIyBQYXJ0aWFsIGRlcml2YXRpdmVzCgpUaGUgZ3JhZGllbnQgdmVjdG9yICRcbmFibGEgRl8yKHgseSkkIGZvciB0aGUgUGVha3MgZnVuY3Rpb24gY29uc2lzdHMgb2YgdGhlIGZvbGxvd2luZyBwYXJ0aWFsIGRlcml2YXRpdmVzOgoKJCQKXGJlZ2lue2FsaWdufQogIFxuYWJsYSBGXzIoeCx5KQogICY9XGJlZ2lue3BtYXRyaXh9CiAgICBcZnJhY3tccGFydGlhbCBGXzJ9e1xwYXJ0aWFsIHh9XFwKICAgIFxmcmFje1xwYXJ0aWFsIEZfMn17XHBhcnRpYWwgeX0KICBcZW5ke3BtYXRyaXh9XFwKICAmPVxiZWdpbntwbWF0cml4fQogICAgLVxmcmFjezJ9ezN9ZV57LVxiaWcoeF4yICsgMiB4ICsgKHkgKyAxKV4yXGJpZyl9CiAgICBcQmlnKAogICAgICBlXnsyeCsyeSsxfVxiaWcoCiAgICAgICAgMzB4XjMtNnheMiszMHgoeV41LTEpKzMKICAgICAgXGJpZykKICAgICAgKwogICAgICA5ZV57Mnh9XGxlZnQoCiAgICAgICB4XjMtMnheMisxCiAgICAgIFxyaWdodCkKICAgICAgKwogICAgICAoeCsxKVxsZWZ0KC1lXnsyeX1ccmlnaHQpCiAgICBcQmlnKVxcCiAgICAtXGZyYWN7Mn17M31lXnstXGJpZyh4XjIrMngrKHkrMSleMlxiaWcpfQogICAgXEJpZygKICAgICAgM3llXnsyeCsyeSsxfVxiaWcoCiAgICAgICAgMTB4XjItMngrNSgyeV4yLTUpeV4zCiAgICAgIFxiaWcpCiAgICAgICsKICAgICAgOWVeezJ4fSgxLXgpXjIoeSsxKQogICAgICAtCiAgICAgIHllXnsyeX0KICAgIFxCaWcpCiAgXGVuZHtwbWF0cml4fQpcZW5ke2FsaWdufQokJAoKVGhlc2UgcGFydGlhbCBkZXJpdmF0aXZlcyBhcmUgZmFyIG1vcmUgY29tcGxleCB0aGFuIHRob3NlIG9mIHRoZSBTaXgtaHVtcCBjYW1lbCBmdW5jdGlvbi4gU2luY2UgYm90aCBvZiB0aGUgb3B0aW1pemF0aW9uIG1ldGhvZHMgd2UgYXJlIHRlc3RpbmcgYXJlIGdyYWRpZW50LWJhc2VkLCBpdCBpcyBsaWtlbHkgdGhhdCBiZW5jaG1hcmtzIGZvciB0aGlzIHRlc3QgZnVuY3Rpb24gd2lsbCB0YWtlIHNpZ25pZmljYW50bHkgbG9uZ2VyLgoKV2l0aCBjb21wbGV4IGRlcml2YXRpdmVzIHN1Y2ggYXMgdGhlc2UgKG9yIHdoZW4gdGhlIGZ1bmN0aW9uIGlzIG5vbi1kaWZmZXJlbnRpYWJsZSBlbnRpcmVseSksIGl0IGlzIG9mdGVuIG1vcmUgcHJlZmVyYWJsZSB0byB1c2UgZGVyaXZhdGl2ZS1mcmVlIG9wdGltaXphdGlvbiBtZXRob2RzW15kZXJpdmF0aXZlLWZyZWVdIHN1Y2ggYXMgdGhlIE5lbGRlci1NZWFkIG1ldGhvZFtebmVsZGVyLW1lYWRdLgoKIyMgT3B0aW1pemF0aW9uIG1ldGhvZHMKCiMjIyBHcmFkaWVudCBkZXNjZW50CgpHcmFkaWVudCBkZXNjZW50IGlzIGEgZ3JhZGllbnQtYmFzZWQgaXRlcmF0aXZlIG9wdGltaXphdGlvbiBtZXRob2QuIEdyYWRpZW50IGRlc2NlbnQgd29ya3MgYnkgaXRlcmF0aXZlbHkgdXBkYXRpbmcgdGhlIGN1cnJlbnQgcG9zaXRpb24gYnkgdGFraW5nIGEgc21hbGwgc3RlcCBpbiB0aGUgZGlyZWN0aW9uIG9mIHN0ZWVwZXN0IGRlc2NlbnRbXmdyYWRpZW50LWRlc2NlbnRdLgoKJCQKXG1hdGhiZnt4fV97aSsxfSBcbGVmdGFycm93IFxtYXRoYmZ7eH1faSAtIFxldGEgXG5hYmxhIEYoXG1hdGhiZnt4fSkKJCQKCj4gKipXaGVyZSoqOgo+Cj4gLSAkXGV0YSQgaXMgdGhlIGxlYXJuaW5nIHJhdGUgZm9yIHRoZSBhbGdvcml0aG0tLS10aGUgc2l6ZSBvZiB0aGUgc3RlcCB0YWtlbiBvbiBlYWNoIGl0ZXJhdGlvbi4KPiAtICRcbmFibGEgRihcbWF0aGJme3h9KSQgaXMgdGhlIGdyYWRpZW50IHZlY3RvciBvZiAkRihcbWF0aGJme3h9KSQsIHdoaWNoIHJlcHJlc2VudHMgdGhlIGRpcmVjdGlvbiBvZiBzdGVlcGVzdCAqKmFzY2VudCoqLgoKV2l0aCBhIGJpdmFyaWF0ZSBmdW5jdGlvbiAkRih4LHkpJCwgd2UgY2FuIHVwZGF0ZSB0aGUgdmVjdG9yICRcYmVnaW57cG1hdHJpeH14IFxcIHlcZW5ke3BtYXRyaXh9JCB3aXRoOgoKJCQKXGJlZ2lue3BtYXRyaXh9CiAgeCBcXCB5ClxlbmR7cG1hdHJpeH0KXGxlZnRhcnJvdwpcYmVnaW57cG1hdHJpeH0KICB4IFxcIHkKXGVuZHtwbWF0cml4fQotXGV0YVxiZWdpbntwbWF0cml4fQogIFxmcmFje1xwYXJ0aWFsIEZ9e1xwYXJ0aWFsIHh9IFxcCiAgXGZyYWN7XHBhcnRpYWwgRn17XHBhcnRpYWwgeX0KXGVuZHtwbWF0cml4fQokJApDaG9vc2luZyB0aGUgbGVhcm5pbmcgcmF0ZSAkXGV0YSQgaXMgYSBmcmVxdWVudCBwcm9ibGVtIGluIG9wdGltaXphdGlvbi0tLXRvbyBsYXJnZSBvZiBhIGxlYXJuaW5nIHJhdGUgc29tZXRpbWVzIGxlYWRzIHRvIGRpdmVyZ2VuY2UgYW5kIG1pc3NpbmcgdGhlIG1pbmltdW0gZHVlIHRvIGhhdmluZyBzdWNoIGxhcmdlIHN0ZXBzLiBDb252ZXJzZWx5LCBhIHZlcnkgc21hbGwgbGVhcm5pbmcgcmF0ZSB3aWxsIHJlcXVpcmUgbWFueSBpdGVyYXRpb25zIHRvIGNvbnZlcmdlLCB3aGljaCBjYW4gYmUgY29zdGx5IGluIHRlcm1zIG9mIHRpbWUgYW5kIENQVS9tZW1vcnkgdXNhZ2UuCgpJbiBvcmRlciB0byBlbnN1cmUgY29udmVyZ2VuY2UsIHdlIHdpbGwgdXNlIGEgc21hbGwgbGVhcm5pbmcgcmF0ZS4KYGBge3J9CiMgU2V0IGEgc21hbGwgbGVhcm5pbmcgcmF0ZQpyYXRlIDwtIDAuMDUKYGBgCgpJdCBpcyBhbHNvIG5lY2Vzc2FyeSB0byBzZXQgYSBtYXhpbXVtIG51bWJlciBvZiBpdGVyYXRpb25zIGZvciBpdGVyYXRpdmUgbWV0aG9kcy4gSW4gdGhlIGV2ZW50IHRoYXQgdGhlIG1ldGhvZCBkaXZlcmdlcywgaXQgd2lsbCBzdGlsbCB0ZXJtaW5hdGUgZXhlY3V0aW9uLiBMaWtld2lzZSwgaWYgJFxldGEkIGlzIHRvbyBzbWFsbCBhbmQgdG9vIG1hbnkgaXRlcmF0aW9ucyBoYXZlIHBhc3NlZCB3aXRob3V0IHJlYWNoaW5nIGEgbWluaW11bSwgdGhlIG1ldGhvZCB3aWxsIHN0b3AuCgpJbiB0aGlzIGNhc2UsIHRoZSBtYXhpbXVtIG51bWJlciBvZiBpdGVyYXRpb25zIHdpbGwgYmUgJDIwMCQuCmBgYHtyfQojIFNldCBtYXhpbXVtIG51bWJlciBvZiBpdGVyYXRpb25zCm1heF9pdGVyYXRpb25zIDwtIDIwMApgYGAKCkluIHRoaXMgbm90ZWJvb2ssIHdlIHdpbGwgc2F5IHRoYXQgYW4gb3B0aW1pemF0aW9uIG1ldGhvZCBjb252ZXJnZXMgdG8gYSBtaW5pbXVtIHBvaW50ICRcYmVnaW57cG1hdHJpeH14XiogXFwgeV4qXGVuZHtwbWF0cml4fSQgaWYgaXQgcmVhY2hlcyBhIHBvaW50ICRcYmVnaW57cG1hdHJpeH14IFxcIHlcZW5ke3BtYXRyaXh9JCBzdWNoIHRoYXQgdGhlIEV1Y2xpZGVhbiBkaXN0YW5jZSAoJExfMiQgbm9ybSkgYmV0d2VlbiB0aGUgdHdvIGlzIGxlc3MgdGhhbiBzb21lICRcZXBzaWxvblxpblxtYXRoYmJ7Ul4rfSQuIEluIG90aGVyIHdvcmRzLCBpZiAkXGJlZ2lue3BtYXRyaXh9eCBcXCB5XGVuZHtwbWF0cml4fSQgaXMgaW4gdGhlICRcZXBzaWxvbiQtbmVpZ2hib3VyaG9vZCBvZiAkXGJlZ2lue3BtYXRyaXh9eF4qIFxcIHleKlxlbmR7cG1hdHJpeH0kOgokJApcbGVmdHxcbGVmdHwKICBcYmVnaW57cG1hdHJpeH14XiogXFwgeV4qXGVuZHtwbWF0cml4fQogIC0KICBcYmVnaW57cG1hdHJpeH14IFxcIHlcZW5ke3BtYXRyaXh9ClxyaWdodHxccmlnaHR8XzIgPCBcZXBzaWxvblxcCiQkCmBgYHtyfQojIFNldCBhIHNtYWxsIGVwc2lsb24KZXBzaWxvbiA8LSAwLjA1CmBgYAoKV2UgZGVmaW5lIHRoZSBncmFkaWVudCBkZXNjZW50IGFsZ29yaXRobSBpdGVyYXRpdmVseSBhczoKYGBge3J9CiMgR3JhZGllbnQgZGVzY2VudAojCiMgUGFyYW1ldGVyczoKIyAgIHguaW5pdGlhbDogVGhlIHN0YXJ0aW5nIHgtY29vcmRpbmF0ZQojICAgeS5pbml0aWFsOiBUaGUgc3RhcnRpbmcgeS1jb29yZGluYXRlCiMgICBGVU46IFRoZSBncmFkaWVudCB2ZWN0b3IgZm9yIHRoZSBmdW5jdGlvbiBiZWluZyBvcHRpbWl6ZWQKIyAgIG1pbmltdW06IFRoZSBhY3R1YWwgbWluaW11bSBvZiB0aGUgZnVuY3Rpb24KIwojIFJldHVybnM6CiMgICBBIHR1cGxlIGNvbnNpc3Rpbmcgb2YgKHRlcm1pbmF0aW9uIHJlYXNvbiwgaXRlcmF0aW9ucykuCiMKZ3JhZGllbnQuZGVzY2VudCA8LSBmdW5jdGlvbih4LmluaXRpYWwsIHkuaW5pdGlhbCwgRlVOLCBtaW5pbXVtKSB7CiAgZm9yIChpdGVyYXRpb25zIGluIDE6bWF4X2l0ZXJhdGlvbnMpIHsKICAgICMgQWRkIHN0YXJ0aW5nIHBvaW50IHRvIHBhdGggaWYgaXQgaXMgdGhlIGZpcnN0IGl0ZXJhdGlvbgogICAgaWYoaXRlcmF0aW9ucyA9PSAxKSBwYXRoW1sxXV0gPDwtIGMoeC5pbml0aWFsLCB5LmluaXRpYWwpCiAgICAKICAgICMgUmV0cmlldmUgY3VycmVudCBwb3NpdGlvbiBmcm9tIHBhdGggdmVjdG9yCiAgICB4LmkgPSBwYXRoW1tpdGVyYXRpb25zXV1bMV0KICAgIHkuaSA9IHBhdGhbW2l0ZXJhdGlvbnNdXVsyXQogICAgCiAgICAjIENoZWNrIGZvciBjb252ZXJnZW5jZQogICAgaWYoZGlzdChyYmluZChjKHguaSwgeS5pKSwgbWluaW11bSkpIDw9IGVwc2lsb24pIHJldHVybihjKCJDb252ZXJnZWQiLCBpdGVyYXRpb25zLTEpKQogICAgCiAgICAjIE1ha2UgYW4gdXBkYXRlIHRvIHRoZSBjdXJyZW50IHBvc2l0aW9uCiAgICB1cGRhdGVkIDwtIGMoeC5pLCB5LmkpIC0gcmF0ZSAqIEZVTih4LmksIHkuaSkKICAgIAogICAgIyBJbmNyZW1lbnQgaXRlcmF0aW9ucyBhbmQgc3RvcmUgdXBkYXRlZCBwb3NpdGlvbiBpbiBgcGF0aGAgdmFyaWFibGUKICAgIGl0ZXJhdGlvbnMgPC0gaXRlcmF0aW9ucyArIDEKICAgIHBhdGhbW2l0ZXJhdGlvbnNdXSA8PC0gdXBkYXRlZAogIH0KICAKICByZXR1cm4oYygiTWF4aW11bSBpdGVyYXRpb25zIHJlYWNoZWQiLCBpdGVyYXRpb25zLTEpKQp9CmBgYAoKPiAqKldoZXJlKio6IGBwYXRoYCBpcyBhIGdsb2JhbCB2YXJpYWJsZSB0aGF0IHN0b3JlcyBhbGwgb2YgdGhlIGludGVybWVkaWF0ZSB2ZWN0b3JzIGR1cmluZyB0aGUgb3B0aW1pemF0aW9uIHByb2Nlc3MuCgojIyMjIFRlc3Rpbmcgb24gdGhlIFNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uCgpCZWZvcmUgd2Ugc3RhcnQgdGVzdGluZywgd2UgbmVlZCBhIG1pbmltdW0gb2YgaW50ZXJlc3QsIGFsb25nIHdpdGggYSBzdGFydGluZyBwb2ludCBmb3IgdGhlIG9wdGltaXphdGlvbiBwcm9jZXNzOgpgYGB7cn0KIyBNaW5pbXVtIG9mIGludGVyZXN0CkYxLm1pbmltdW0gPC0gYygwLjA4OTg0MiwgLTAuNzEyNjU2KQoKIyBTdGFydGluZyBwb2ludApGMS5zdGFydCA8LSBjKDAuODUsIDApCmBgYAoKQWRkaXRpb25hbGx5LCB3ZSB3aWxsIG5lZWQgdG8gaW5pdGlhbGl6ZSB0aGUgYHBhdGhgIHZhcmlhYmxlIGZvciBrZWVwaW5nIHRyYWNrIG9mIHRoZSB1cGRhdGVkIHZlY3RvcnMgZHVyaW5nIHRoZSBvcHRpbWl6YXRpb24gcHJvY2Vzcy4gVGhpcyB2YXJpYWJsZSB3aWxsIGJlIHJldXNlZCBmb3Igb3RoZXIgdGVzdHMsIHNvIHdlIHdpbGwgYWxzbyBkZWZpbmUgYSByZXNldCBmdW5jdGlvbi4KYGBge3J9CiMgQ3JlYXRlIGFuIGVtcHR5IHBhdGggdmVjdG9yCnBhdGggPDwtIHZlY3RvcignbGlzdCcsIG1heF9pdGVyYXRpb25zKQojIFJlc2V0IGZ1bmN0aW9uIGZvciB0aGUgYHBhdGhgIHZhcmlhYmxlCnJlc2V0X3BhdGggPC0gZnVuY3Rpb24oKSB7IHBhdGggPDwtIHZlY3RvcignbGlzdCcsIG1heF9pdGVyYXRpb25zKSB9CmBgYAoKUnVubmluZyB0aGUgZ3JhZGllbnQgZGVzY2VudCBtZXRob2QgKHdpdGggYmVuY2htYXJraW5nKToKYGBge3J9CiMgUnVuIHRpbWVkIGdyYWRpZW50IGRlc2NlbnQKRjEuZ3JhZGllbnQudGltZSA8LSBwcm9jLnRpbWUoKQpGMS5ncmFkaWVudC5yZXN1bHRzIDwtIGdyYWRpZW50LmRlc2NlbnQoRjEuc3RhcnRbMV0sIEYxLnN0YXJ0WzJdLCBGMS5kLCBGMS5taW5pbXVtKQpGMS5ncmFkaWVudC50aW1lIDwtIHByb2MudGltZSgpIC0gRjEuZ3JhZGllbnQudGltZQpgYGAKClBsb3R0aW5nIHRoZSBjb250b3VyIGFuZCBwYXRoIG9mIHVwZGF0ZXM6CmBgYHtyLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQojIENvbnZlcnQgdGhlIGBwYXRoYCB2YXJpYWJsZSB0byBhIG1hdHJpeApwYXRoIDwtIG1hdHJpeCh1bmxpc3QocGF0aCksIG5jb2w9MiwgYnlyb3c9VFJVRSkKCiMgRGlzcGxheSBjb250b3VyIGFuZCBvcHRpbWl6YXRpb24gcGF0aApGMS5ncmFkaWVudC5jb250b3VyIDwtIHBsb3RfbHkoeD1+RjEueCwgeT1+RjEueSwgej1GMS56LCB3aWR0aD04MDAsIGhlaWdodD01MDAsCiAgICAgICAgICAgICAgICAgICAgICB0eXBlPSJjb250b3VyIiwgY29udG91cnM9bGlzdChzaG93bGFiZWxzID0gVFJVRSkpICU+JQoKICAjIEFkZCBvcHRpbWl6YXRpb24gcGF0aCB0cmFjZQogIGFkZF90cmFjZSh4PXBhdGhbLDFdLCB5PXBhdGhbLDJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iT3B0aW1pemF0aW9uIHBhdGgiLCBtb2RlPSJsaW5lIikgJT4lCgogICMgQWRkIGNyb3NzIGF0IHRhcmdldCBtaW5pbXVtIHBvc2l0aW9uCiAgYWRkX3RyYWNlKHg9RjEubWluaW11bVsxXSwgeT1GMS5taW5pbXVtWzJdLCB0eXBlPSJzY2F0dGVyIiwgbmFtZT0iVGFyZ2V0IG1pbmltdW0iLAogICAgICAgICAgICBtb2RlPSJtYXJrZXJzIiwgbWFya2VyPWxpc3QoY29sb3I9IiM1ZWM0YTciLCBzaXplPTYsIHN5bWJvbD0ieCIpKSAlPiUKCiAgIyBBZGQgYXJyb3cgYW5kIGFubm90YXRpb24gZm9yIHN0YXJ0aW5nIHBvc2l0aW9uCiAgYWRkX2Fubm90YXRpb25zKHg9RjEuc3RhcnRbMV0sIHk9RjEuc3RhcnRbMl0sIHRleHQ9IlN0YXJ0IiwKICAgICAgICAgICAgICAgICAgc2hvd2Fycm93PVRSVUUsIGFycm93aGVhZD00LCBhcnJvd3NpemU9LjUsIGFycm93Y29sb3I9J3doaXRlJywgYXg9MzAsIGF5PS0zMCwKICAgICAgICAgICAgICAgICAgZm9udD1saXN0KGNvbG9yID0gJyM4MWNjYzInLCBmYW1pbHk9J2hlbHZldGljYScsIHNpemUgPSAxNCkpICU+JQoKICAjIEFkZCBhcnJvdyBhbmQgYW5ub3RhdGlvbiBmb3IgdGFyZ2V0IG1pbmltdW0KICBhZGRfYW5ub3RhdGlvbnMoeD1GMS5taW5pbXVtWzFdLCB5PUYxLm1pbmltdW1bMl0sIHRleHQ9IlRhcmdldFxubWluaW11bSIsCiAgICAgICAgICAgICAgICAgIHNob3dhcnJvdz1UUlVFLCBhcnJvd2hlYWQ9NCwgYXJyb3dzaXplPS41LCBhcnJvd2NvbG9yPSd3aGl0ZScsIGF4PS04MCwgYXk9LTMwLAogICAgICAgICAgICAgICAgICBmb250PWxpc3QoY29sb3IgPSAnIzgxY2NjMicsIGZhbWlseT0naGVsdmV0aWNhJywgc2l6ZSA9IDE0KSkgJT4lCgogICMgQWRkaW5nIGFuZCBwb3NpdGlvbmluZyBwbG90IHRpdGxlCiAgbGF5b3V0KHRpdGxlPSJHRCBvcHRpbWl6YXRpb24gb2YgdGhlIHNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uIChGMSkiLCBtYXJnaW49bGlzdChsPTEyNSwgcj0wLCB0PTYwLCBiPTYwKSkKCiMgRGlzcGxheSB0aGUgY29udG91ciBwbG90CmRpdihGMS5ncmFkaWVudC5jb250b3VyLCBhbGlnbj0iY2VudGVyIikKYGBgCgpUZXJtaW5hdGlvbiByZWFzb24gYW5kIG51bWJlciBvZiBpdGVyYXRpb25zOgpgYGB7cn0KY2F0KHNwcmludGYoIlRlcm1pbmF0aW9uIHJlYXNvbjogJXNcbk51bWJlciBvZiBpdGVyYXRpb25zOiAlcyIsIEYxLmdyYWRpZW50LnJlc3VsdHNbMV0sIEYxLmdyYWRpZW50LnJlc3VsdHNbMl0pKQpgYGAKCkJlbmNobWFya2luZyBmb3IgdGhlc2Ugb3B0aW1pemF0aW9uIG1ldGhvZHMgd2lsbCBiZSBkb25lIHdpdGggdGhlIGBwcm9jLnRpbWVgIGJhc2UgZnVuY3Rpb24gaW4gUltecHJvYy10aW1lXS4gVGhpcyBmdW5jdGlvbiByZWNvcmRzIHRoZSB0aW1lIHRha2VuIGZvciBhIHNwZWNpZmljIGFjdGlvbiB0byBmaW5pc2ggZXhlY3V0aW9uLCBhY2NvcmRpbmcgdGhyZWUgZGlmZmVyZW50IHRpbWUgbWVhc3VyZXM6CgoxLiBgdXNlcmA6IFRoZSBDUFUgdGltZSBjaGFyZ2VkIGZvciB0aGUgZXhlY3V0aW9uIG9mIHVzZXIgaW5zdHJ1Y3Rpb25zIG9mIHRoZSBjYWxsaW5nIHByb2Nlc3MuCjIuIGBzeXN0ZW1gOiBUaGUgQ1BVIHRpbWUgY2hhcmdlZCBmb3IgZXhlY3V0aW9uIGJ5IHRoZSBzeXN0ZW0gb24gYmVoYWxmIG9mIHRoZSBjYWxsaW5nIHByb2Nlc3MuCjMuIGBlbGFwc2VkYDogVGhlICJyZWFsIiBlbGFwc2VkIHRpbWUgc2luY2UgdGhlIHByb2Nlc3Mgd2FzIHN0YXJ0ZWQuCgpQcmludGluZyB0aGUgYHByb2NfdGltZWAgcmVzdWx0IGRpc3BsYXlzIHRoZXNlIG1lYXN1cmVzIGluIG9yZGVyOgpgYGB7cn0KcHJpbnQoRjEuZ3JhZGllbnQudGltZSkKYGBgCgojIyMjIFRlc3Rpbmcgb24gdGhlIFBlYWtzIGZ1bmN0aW9uCgpTZXR0aW5nIGEgbWluaW11bSBvZiBpbnRlcmVzdCwgYWxvbmcgd2l0aCBhIHN0YXJ0aW5nIHBvaW50OgpgYGB7cn0KIyBNaW5pbXVtIG9mIGludGVyZXN0CkYyLm1pbmltdW0gPC0gYygwLjIyODI3OTk5OTk3OTIzNywgLTEuNjI1NTMxMDcxOTU0NDY0KQoKIyBTdGFydGluZyBwb2ludApGMi5zdGFydCA8LSBjKDEsIC0wLjIpCmBgYAoKUmVzZXR0aW5nIHRoZSBvcHRpbWl6YXRpb24gcGF0aCB2YXJpYWJsZSAoYHBhdGhgKSBhbmQgcnVubmluZyB0aGUgZ3JhZGllbnQgZGVzY2VudCBtZXRob2QgKHdpdGggYmVuY2htYXJraW5nKToKYGBge3J9CiMgUmVzZXR0aW5nIG9wdGltaXphdGlvbiBwYXRoCnJlc2V0X3BhdGgoKQoKIyBSdW4gdGltZWQgZ3JhZGllbnQgZGVzY2VudApGMi5ncmFkaWVudC50aW1lIDwtIHByb2MudGltZSgpCkYyLmdyYWRpZW50LnJlc3VsdHMgPC0gZ3JhZGllbnQuZGVzY2VudChGMi5zdGFydFsxXSwgRjIuc3RhcnRbMl0sIEYyLmQsIEYyLm1pbmltdW0pCkYyLmdyYWRpZW50LnRpbWUgPC0gcHJvYy50aW1lKCkgLSBGMi5ncmFkaWVudC50aW1lCmBgYAoKUGxvdHRpbmcgdGhlIGNvbnRvdXIgYW5kIHBhdGggb2YgdXBkYXRlczoKYGBge3IsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0V9CiMgQ29udmVydCB0aGUgYHBhdGhgIHZhcmlhYmxlIHRvIGEgbWF0cml4CnBhdGggPC0gbWF0cml4KHVubGlzdChwYXRoKSwgbmNvbD0yLCBieXJvdz1UUlVFKQoKIyBEaXNwbGF5IGNvbnRvdXIgYW5kIG9wdGltaXphdGlvbiBwYXRoCkYyLmdyYWRpZW50LmNvbnRvdXIgPC0gcGxvdF9seSh4PX5GMi54LCB5PX5GMi55LCB6PUYyLnosIHdpZHRoPTcwMCwgaGVpZ2h0PTYwMCwKICAgICAgICAgICAgICAgICAgICAgIHR5cGU9ImNvbnRvdXIiLCBjb250b3Vycz1saXN0KHNob3dsYWJlbHMgPSBUUlVFKSkgJT4lCgogICMgQWRkIG9wdGltaXphdGlvbiBwYXRoIHRyYWNlCiAgYWRkX3RyYWNlKHg9cGF0aFssMV0sIHk9cGF0aFssMl0sIHR5cGU9InNjYXR0ZXIiLCBuYW1lPSJPcHRpbWl6YXRpb24gcGF0aCIsIG1vZGU9ImxpbmUiKSAlPiUKCiAgIyBBZGQgY3Jvc3MgYXQgdGFyZ2V0IG1pbmltdW0gcG9zaXRpb24KICBhZGRfdHJhY2UoeD1GMi5taW5pbXVtWzFdLCB5PUYyLm1pbmltdW1bMl0sIHR5cGU9InNjYXR0ZXIiLCBuYW1lPSJUYXJnZXQgbWluaW11bSIsCiAgICAgICAgICAgIG1vZGU9Im1hcmtlcnMiLCBtYXJrZXI9bGlzdChjb2xvcj0iIzVlYzRhNyIsIHNpemU9Niwgc3ltYm9sPSJ4IikpICU+JQoKICAjIEFkZCBhcnJvdyBhbmQgYW5ub3RhdGlvbiBmb3Igc3RhcnRpbmcgcG9zaXRpb24KICBhZGRfYW5ub3RhdGlvbnMoeD1GMi5zdGFydFsxXSwgeT1GMi5zdGFydFsyXSwgdGV4dD0iU3RhcnQiLAogICAgICAgICAgICAgICAgICBzaG93YXJyb3c9VFJVRSwgYXJyb3doZWFkPTQsIGFycm93c2l6ZT0uNSwgYXJyb3djb2xvcj0nd2hpdGUnLCBheD0tNSwgYXk9LTQwLAogICAgICAgICAgICAgICAgICBmb250PWxpc3QoY29sb3IgPSAnIzgxY2NjMicsIGZhbWlseT0naGVsdmV0aWNhJywgc2l6ZSA9IDE0KSkgJT4lCgogICMgQWRkIGFycm93IGFuZCBhbm5vdGF0aW9uIGZvciB0YXJnZXQgbWluaW11bQogIGFkZF9hbm5vdGF0aW9ucyh4PUYyLm1pbmltdW1bMV0sIHk9RjIubWluaW11bVsyXSwgdGV4dD0iVGFyZ2V0XG5taW5pbXVtIiwKICAgICAgICAgICAgICAgICAgc2hvd2Fycm93PVRSVUUsIGFycm93aGVhZD00LCBhcnJvd3NpemU9LjUsIGFycm93Y29sb3I9J3doaXRlJywgYXg9LTgwLCBheT0zMCwKICAgICAgICAgICAgICAgICAgZm9udD1saXN0KGNvbG9yID0gJyM4MWNjYzInLCBmYW1pbHk9J2hlbHZldGljYScsIHNpemUgPSAxNCkpICU+JQoKICAjIEFkZGluZyBhbmQgcG9zaXRpb25pbmcgcGxvdCB0aXRsZQogIGxheW91dCh0aXRsZT0iR0Qgb3B0aW1pemF0aW9uIG9mIHRoZSBwZWFrcyBmdW5jdGlvbiAoRjIpIiwgbWFyZ2luPWxpc3QobD0xMjUsIHI9MCwgdD02MCwgYj02MCkpCgojIERpc3BsYXkgdGhlIGNvbnRvdXIgcGxvdApkaXYoRjIuZ3JhZGllbnQuY29udG91ciwgYWxpZ249ImNlbnRlciIpCmBgYAoKVGVybWluYXRpb24gcmVhc29uIGFuZCBudW1iZXIgb2YgaXRlcmF0aW9uczoKYGBge3J9CmNhdChzcHJpbnRmKCJUZXJtaW5hdGlvbiByZWFzb246ICVzXG5OdW1iZXIgb2YgaXRlcmF0aW9uczogJXMiLCBGMi5ncmFkaWVudC5yZXN1bHRzWzFdLCBGMi5ncmFkaWVudC5yZXN1bHRzWzJdKSkKYGBgCgpCZW5jaG1hcmtzOgpgYGB7cn0KcHJpbnQoRjIuZ3JhZGllbnQudGltZSkKYGBgCgojIyMgQ29vcmRpbmF0ZSBkZXNjZW50CgpHcmFkaWVudC1iYXNlZCBjb29yZGluYXRlIGRlc2NlbnQgaXMgYSBzaW1pbGFyIG1ldGhvZCBvZiBvcHRpbWl6YXRpb24gdG8gZ3JhZGllbnQgZGVzY2VudCwgYXMgZWFjaCBpdGVyYXRpb24gc3RpbGwgdXBkYXRlcyB0aGUgcG9zaXRpb24gYnkgbW92aW5nIChieSBhIHN0ZXAgc2l6ZSAkXGV0YSQpIGluIHRoZSBkaXJlY3Rpb24gb2Ygc3RlZXBlc3QgZGVzY2VudC4KCkhvd2V2ZXIsIHRoZSBtYWluIGRpZmZlcmVuY2Ugd2l0aCBjb29yZGluYXRlIGRlc2NlbnQgaXMgdGhhdCB3ZSBvcHRpbWl6ZSBvbmUgY29vcmRpbmF0ZSBhdCBhIHRpbWUtLS1lc3NlbnRpYWxseSBzb2x2aW5nICRkJCB1bml2YXJpYXRlIG9wdGltaXphdGlvbiBwcm9ibGVtcyAoaWYgdGhlIGZ1bmN0aW9uICRGJCBpcyAkZCQtdmFyaWF0ZSkuIFRoZSBvcHRpbWl6YXRpb24gcGF0aHMgZnJvbSB0aGVzZSBzdWItcHJvYmxlbXMgYXJlIHRoZW4gY29tYmluZWQgdG8gZm9ybSBhIHNvbHV0aW9uIHRvIHRoZSBvcmlnaW5hbCBvcHRpbWl6YXRpb24gcHJvYmxlbS4KCkZvciBhIHNpbmdsZSBjb29yZGluYXRlICRpJCwgdGhlIGl0ZXJhdGl2ZSB1cGRhdGUgZm9ybXVsYSBpcyBnaXZlbiBieToKJCQKeF97aSsxfSBcbGVmdGFycm93IHhfaSAtIFxldGEgXGZyYWN7XHBhcnRpYWx9e1xwYXJ0aWFsIHhfaX1GKFxtYXRoYmZ7eH0pCiQkCgpXZSBkZWZpbmUgdGhlIGNvb3JkaW5hdGUgZGVzY2VudCBhbGdvcml0aG0gaXRlcmF0aXZlbHkgYXM6CmBgYHtyfQojIENvb3JkaW5hdGUgZGVzY2VudAojCiMgUGFyYW1ldGVyczoKIyAgIHguaW5pdGlhbDogVGhlIHN0YXJ0aW5nIHgtY29vcmRpbmF0ZQojICAgeS5pbml0aWFsOiBUaGUgc3RhcnRpbmcgeS1jb29yZGluYXRlCiMgICBGVU46IFRoZSBncmFkaWVudCB2ZWN0b3IgZm9yIHRoZSBmdW5jdGlvbiBiZWluZyBvcHRpbWl6ZWQKIyAgIG1pbmltdW06IFRoZSBhY3R1YWwgbWluaW11bSBvZiB0aGUgZnVuY3Rpb24KIwojIFJldHVybnM6CiMgICBBIHR1cGxlIGNvbnNpc3Rpbmcgb2YgKHRlcm1pbmF0aW9uIHJlYXNvbiwgaXRlcmF0aW9ucykuCiMKY29vcmRpbmF0ZS5kZXNjZW50IDwtIGZ1bmN0aW9uKHguaW5pdGlhbCwgeS5pbml0aWFsLCBGVU4sIG1pbmltdW0pIHsKICBmb3IgKGl0ZXJhdGlvbnMgaW4gMTptYXhfaXRlcmF0aW9ucykgewogICAgIyBBZGQgc3RhcnRpbmcgcG9pbnQgdG8gcGF0aCBpZiBpdCBpcyB0aGUgZmlyc3QgaXRlcmF0aW9uCiAgICBpZihpdGVyYXRpb25zID09IDEpIHBhdGhbWzFdXSA8PC0gYyh4LmluaXRpYWwsIHkuaW5pdGlhbCkKICAgIAogICAgIyBSZXRyaWV2ZSBjdXJyZW50IHBvc2l0aW9uIGZyb20gcGF0aCB2ZWN0b3IKICAgIHguaSA9IHBhdGhbW2l0ZXJhdGlvbnNdXVsxXQogICAgeS5pID0gcGF0aFtbaXRlcmF0aW9uc11dWzJdCiAgICAKICAgICMgQ2hlY2sgZm9yIGNvbnZlcmdlbmNlCiAgICBpZihkaXN0KHJiaW5kKGMoeC5pLCB5LmkpLCBtaW5pbXVtKSkgPD0gZXBzaWxvbikgcmV0dXJuKGMoIkNvbnZlcmdlZCIsIGl0ZXJhdGlvbnMtMSkpCiAgICAKICAgICMgTWFrZSBhbiB1cGRhdGUgdG8gdGhlIGN1cnJlbnQgcG9zaXRpb24KICAgIHVwZGF0ZWQgPC0gTlVMTAogICAgaWYoKGl0ZXJhdGlvbnMgJSUgMikgPT0gMSkgewogICAgICB1cGRhdGVkIDwtIGMoeC5pLCB5LmkpIC0gcmF0ZSAqIGMoRlVOKHguaSwgeS5pKVsxXSwgMCkKICAgIH0gZWxzZSB7CiAgICAgIHVwZGF0ZWQgPC0gYyh4LmksIHkuaSkgLSByYXRlICogYygwLCBGVU4oeC5pLCB5LmkpWzJdKQogICAgfQogICAgCiAgICAjIEluY3JlbWVudCBpdGVyYXRpb25zIGFuZCBzdG9yZSB1cGRhdGVkIHBvc2l0aW9uIGluIGBwYXRoYCB2YXJpYWJsZQogICAgaXRlcmF0aW9ucyA8LSBpdGVyYXRpb25zICsgMQogICAgcGF0aFtbaXRlcmF0aW9uc11dIDw8LSB1cGRhdGVkCiAgfQogIAogIHJldHVybihjKCJNYXhpbXVtIGl0ZXJhdGlvbnMgcmVhY2hlZCIsIGl0ZXJhdGlvbnMtMSkpCn0KYGBgCgojIyMjIFRlc3Rpbmcgb24gdGhlIFNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uCgpSdW5uaW5nIHRoZSBjb29yZGluYXRlIGRlc2NlbnQgbWV0aG9kICh3aXRoIGJlbmNobWFya2luZyk6CmBgYHtyfQojIFJlc2V0IG9wdGltaXphdGlvbiBwYXRoCnJlc2V0X3BhdGgoKQoKIyBSdW4gdGltZWQgY29vcmRpbmF0ZSBkZXNjZW50CkYxLmNvb3JkaW5hdGUudGltZSA8LSBwcm9jLnRpbWUoKQpGMS5jb29yZGluYXRlLnJlc3VsdHMgPC0gY29vcmRpbmF0ZS5kZXNjZW50KEYxLnN0YXJ0WzFdLCBGMS5zdGFydFsyXSwgRjEuZCwgRjEubWluaW11bSkKRjEuY29vcmRpbmF0ZS50aW1lIDwtIHByb2MudGltZSgpIC0gRjEuY29vcmRpbmF0ZS50aW1lCgojIFJldHJpZXZlIG51bWJlciBvZiBpdGVyYXRpb25zCkYxLmNvb3JkaW5hdGUuaXRlcmF0aW9ucyA8LSBhcy5udW1lcmljKEYxLmNvb3JkaW5hdGUucmVzdWx0c1tbMl1dKQpgYGAKClRlcm1pbmF0aW9uIHJlYXNvbiBhbmQgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgZm9yIGNvb3JkaW5hdGUgZGVzY2VudCBvcHRpbWl6YXRpb246CmBgYHtyfQpjYXQoc3ByaW50ZigiVGVybWluYXRpb24gcmVhc29uOiAlc1xuTnVtYmVyIG9mIGl0ZXJhdGlvbnM6ICVzIiwgRjEuY29vcmRpbmF0ZS5yZXN1bHRzWzFdLCBGMS5jb29yZGluYXRlLnJlc3VsdHNbMl0pKQpgYGAKCkJlbmNobWFya3MgZm9yIGNvb3JkaW5hdGUgZGVzY2VudCBvcHRpbWl6YXRpb246CmBgYHtyfQpwcmludChGMS5jb29yZGluYXRlLnRpbWUpCmBgYAoKUGxvdHRpbmcgdGhlIGNvbnRvdXIgYW5kIHBhdGggb2YgdXBkYXRlczoKYGBge3IsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0V9CiMgQ29udmVydCB0aGUgYHBhdGhgIHZhcmlhYmxlIHRvIGEgbWF0cml4CnBhdGggPC0gbWF0cml4KHVubGlzdChwYXRoKSwgbmNvbD0yLCBieXJvdz1UUlVFKQoKIyBEaXNwbGF5IGNvbnRvdXIgYW5kIG9wdGltaXphdGlvbiBwYXRoCkYxLmNvb3JkaW5hdGUuY29udG91ciA8LSBwbG90X2x5KHg9fkYxLngsIHk9fkYxLnksIHo9RjEueiwgd2lkdGg9ODAwLCBoZWlnaHQ9NTAwLAogICAgICAgICAgICAgICAgICAgICAgdHlwZT0iY29udG91ciIsIGNvbnRvdXJzPWxpc3Qoc2hvd2xhYmVscyA9IFRSVUUpKSAlPiUKCiAgIyBBZGQgb3B0aW1pemF0aW9uIHBhdGggdHJhY2UKICBhZGRfdHJhY2UoeD1wYXRoWywxXSwgeT1wYXRoWywyXSwgdHlwZT0ic2NhdHRlciIsIG5hbWU9Ik9wdGltaXphdGlvbiBwYXRoIiwgbW9kZT0ibGluZSIpICU+JQoKICAjIEFkZCBjcm9zcyBhdCB0YXJnZXQgbWluaW11bSBwb3NpdGlvbgogIGFkZF90cmFjZSh4PUYxLm1pbmltdW1bMV0sIHk9RjEubWluaW11bVsyXSwgdHlwZT0ic2NhdHRlciIsIG5hbWU9IlRhcmdldCBtaW5pbXVtIiwKICAgICAgICAgICAgbW9kZT0ibWFya2VycyIsIG1hcmtlcj1saXN0KGNvbG9yPSIjNWVjNGE3Iiwgc2l6ZT02LCBzeW1ib2w9IngiKSkgJT4lCgogICMgQWRkIGFycm93IGFuZCBhbm5vdGF0aW9uIGZvciBzdGFydGluZyBwb3NpdGlvbgogIGFkZF9hbm5vdGF0aW9ucyh4PUYxLnN0YXJ0WzFdLCB5PUYxLnN0YXJ0WzJdLCB0ZXh0PSJTdGFydCIsCiAgICAgICAgICAgICAgICAgIHNob3dhcnJvdz1UUlVFLCBhcnJvd2hlYWQ9NCwgYXJyb3dzaXplPS41LCBhcnJvd2NvbG9yPSd3aGl0ZScsIGF4PTMwLCBheT0tMzAsCiAgICAgICAgICAgICAgICAgIGZvbnQ9bGlzdChjb2xvciA9ICcjODFjY2MyJywgZmFtaWx5PSdoZWx2ZXRpY2EnLCBzaXplID0gMTQpKSAlPiUKCiAgIyBBZGQgYXJyb3cgYW5kIGFubm90YXRpb24gZm9yIHRhcmdldCBtaW5pbXVtCiAgYWRkX2Fubm90YXRpb25zKHg9RjEubWluaW11bVsxXSwgeT1GMS5taW5pbXVtWzJdLCB0ZXh0PSJUYXJnZXRcbm1pbmltdW0iLAogICAgICAgICAgICAgICAgICBzaG93YXJyb3c9VFJVRSwgYXJyb3doZWFkPTQsIGFycm93c2l6ZT0uNSwgYXJyb3djb2xvcj0nd2hpdGUnLCBheD0tODAsIGF5PS0zMCwKICAgICAgICAgICAgICAgICAgZm9udD1saXN0KGNvbG9yID0gJyM4MWNjYzInLCBmYW1pbHk9J2hlbHZldGljYScsIHNpemUgPSAxNCkpICU+JQoKICAjIEFkZGluZyBhbmQgcG9zaXRpb25pbmcgcGxvdCB0aXRsZQogIGxheW91dCh0aXRsZT0iQ0Qgb3B0aW1pemF0aW9uIG9mIHRoZSBzaXgtaHVtcCBjYW1lbCBmdW5jdGlvbiAoRjEpIiwgbWFyZ2luPWxpc3QobD0xMjUsIHI9MCwgdD02MCwgYj02MCkpCgojIERpc3BsYXkgdGhlIGNvbnRvdXIgcGxvdApkaXYoRjEuY29vcmRpbmF0ZS5jb250b3VyLCBhbGlnbj0iY2VudGVyIikKYGBgCgojIyMjIFRlc3Rpbmcgb24gdGhlIFBlYWtzIGZ1bmN0aW9uCgpSdW5uaW5nIHRoZSBjb29yZGluYXRlIGRlc2NlbnQgbWV0aG9kICh3aXRoIGJlbmNobWFya2luZyk6CmBgYHtyfQojIFJlc2V0IG9wdGltaXphdGlvbiBwYXRoCnJlc2V0X3BhdGgoKQoKIyBSdW4gdGltZWQgeC1jb29yZGluYXRlIGRlc2NlbnQKRjIuY29vcmRpbmF0ZS50aW1lIDwtIHByb2MudGltZSgpCkYyLmNvb3JkaW5hdGUucmVzdWx0cyA8LSBjb29yZGluYXRlLmRlc2NlbnQoRjIuc3RhcnRbMV0sIEYyLnN0YXJ0WzJdLCBGMi5kLCBGMi5taW5pbXVtKQpGMi5jb29yZGluYXRlLnRpbWUgPC0gcHJvYy50aW1lKCkgLSBGMi5jb29yZGluYXRlLnRpbWUKCiMgVHJ1Y2F0ZSBOVUxMcyBpbiBvcHRpbWl6YXRpb24gcGF0aCBsaXN0CkYyLmNvb3JkaW5hdGUucGF0aCA8LSBGaWx0ZXIoTmVnYXRlKGlzLm51bGwpLCBwYXRoKQoKIyBSZXRyaWV2ZSBudW1iZXIgb2YgaXRlcmF0aW9ucwpGMi5jb29yZGluYXRlLml0ZXJhdGlvbnMgPC0gYXMubnVtZXJpYyhGMi5jb29yZGluYXRlLnJlc3VsdHNbWzJdXSkKYGBgCgpUZXJtaW5hdGlvbiByZWFzb24gYW5kIG51bWJlciBvZiBpdGVyYXRpb25zIGZvciBjb29yZGluYXRlIGRlc2NlbnQgb3B0aW1pemF0aW9uOgpgYGB7cn0KY2F0KHNwcmludGYoIlRlcm1pbmF0aW9uIHJlYXNvbjogJXNcbk51bWJlciBvZiBpdGVyYXRpb25zOiAlcyIsIEYyLmNvb3JkaW5hdGUucmVzdWx0c1sxXSwgRjIuY29vcmRpbmF0ZS5yZXN1bHRzWzJdKSkKYGBgCgpCZW5jaG1hcmtzIGZvciBjb29yZGluYXRlIGRlc2NlbnQgb3B0aW1pemF0aW9uOgpgYGB7cn0KcHJpbnQoRjIuY29vcmRpbmF0ZS50aW1lKQpgYGAKClBsb3R0aW5nIHRoZSBjb250b3VyIGFuZCBwYXRoIG9mIHVwZGF0ZXM6CmBgYHtyLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQojIENvbnZlcnQgdGhlIGBwYXRoYCB2YXJpYWJsZSB0byBhIG1hdHJpeApwYXRoIDwtIG1hdHJpeCh1bmxpc3QocGF0aCksIG5jb2w9MiwgYnlyb3c9VFJVRSkKCiMgRGlzcGxheSBjb250b3VyIGFuZCBvcHRpbWl6YXRpb24gcGF0aApGMi5jb29yZGluYXRlLmNvbnRvdXIgPC0gcGxvdF9seSh4PX5GMi54LCB5PX5GMi55LCB6PUYyLnosIHdpZHRoPTcwMCwgaGVpZ2h0PTYwMCwKICAgICAgICAgICAgICAgICAgICAgIHR5cGU9ImNvbnRvdXIiLCBjb250b3Vycz1saXN0KHNob3dsYWJlbHMgPSBUUlVFKSkgJT4lCgogICMgQWRkIG9wdGltaXphdGlvbiBwYXRoIHRyYWNlCiAgYWRkX3RyYWNlKHg9cGF0aFssMV0sIHk9cGF0aFssMl0sIHR5cGU9InNjYXR0ZXIiLCBuYW1lPSJPcHRpbWl6YXRpb24gcGF0aCIsIG1vZGU9ImxpbmUiKSAlPiUKCiAgIyBBZGQgY3Jvc3MgYXQgdGFyZ2V0IG1pbmltdW0gcG9zaXRpb24KICBhZGRfdHJhY2UoeD1GMi5taW5pbXVtWzFdLCB5PUYyLm1pbmltdW1bMl0sIHR5cGU9InNjYXR0ZXIiLCBuYW1lPSJUYXJnZXQgbWluaW11bSIsCiAgICAgICAgICAgIG1vZGU9Im1hcmtlcnMiLCBtYXJrZXI9bGlzdChjb2xvcj0iIzVlYzRhNyIsIHNpemU9Niwgc3ltYm9sPSJ4IikpICU+JQoKICAjIEFkZCBhcnJvdyBhbmQgYW5ub3RhdGlvbiBmb3Igc3RhcnRpbmcgcG9zaXRpb24KICBhZGRfYW5ub3RhdGlvbnMoeD1GMi5zdGFydFsxXSwgeT1GMi5zdGFydFsyXSwgdGV4dD0iU3RhcnQiLAogICAgICAgICAgICAgICAgICBzaG93YXJyb3c9VFJVRSwgYXJyb3doZWFkPTQsIGFycm93c2l6ZT0uNSwgYXJyb3djb2xvcj0nd2hpdGUnLCBheD0zMCwgYXk9LTMwLAogICAgICAgICAgICAgICAgICBmb250PWxpc3QoY29sb3IgPSAnIzgxY2NjMicsIGZhbWlseT0naGVsdmV0aWNhJywgc2l6ZSA9IDE0KSkgJT4lCgogICMgQWRkIGFycm93IGFuZCBhbm5vdGF0aW9uIGZvciB0YXJnZXQgbWluaW11bQogIGFkZF9hbm5vdGF0aW9ucyh4PUYyLm1pbmltdW1bMV0sIHk9RjIubWluaW11bVsyXSwgdGV4dD0iVGFyZ2V0XG5taW5pbXVtIiwKICAgICAgICAgICAgICAgICAgc2hvd2Fycm93PVRSVUUsIGFycm93aGVhZD00LCBhcnJvd3NpemU9LjUsIGFycm93Y29sb3I9J3doaXRlJywgYXg9LTgwLCBheT0tMzAsCiAgICAgICAgICAgICAgICAgIGZvbnQ9bGlzdChjb2xvciA9ICcjODFjY2MyJywgZmFtaWx5PSdoZWx2ZXRpY2EnLCBzaXplID0gMTQpKSAlPiUKCiAgIyBBZGRpbmcgYW5kIHBvc2l0aW9uaW5nIHBsb3QgdGl0bGUKICBsYXlvdXQodGl0bGU9IkNEIG9wdGltaXphdGlvbiBvZiB0aGUgcGVha3MgZnVuY3Rpb24gKEYyKSIsIG1hcmdpbj1saXN0KGw9MTI1LCByPTAsIHQ9NjAsIGI9NjApKQoKIyBEaXNwbGF5IHRoZSBjb250b3VyIHBsb3QKZGl2KEYyLmNvb3JkaW5hdGUuY29udG91ciwgYWxpZ249ImNlbnRlciIpCmBgYAoKIyBNZXRob2QgY29tcGFyaXNvbiBtZXRyaWNzCgojIyBCZW5jaG1hcmtzCgpQcmVwYXJpbmcgdGhlIGJlbmNobWFyayBjb21wYXJpc29uIHBsb3Q6CmBgYHtyLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQojIERhdGFmcmFtZSByZXByZXNlbnRpbmcgdGhlIGdyYWRpZW50IGFuZCBjb29yZGluYXRlIGRlc2NlbnQgYmVuY2htYXJrcyBvbiBGMQpGMS5iZW5jaG1hcmtzLmRmIDwtIGRhdGEuZnJhbWUoCiAgTWV0aG9kPXJlcChjKCJHcmFkaWVudCBkZXNjZW50IiwgIkNvb3JkaW5hdGUgZGVzY2VudCIpLCBlYWNoPTMpLAogIFR5cGU9YygiVXNlciIsICJTeXN0ZW0iLCAiRWxhcHNlZCAoVG90YWwpIiksCiAgVGltZT1yb3VuZChjKEYxLmdyYWRpZW50LnRpbWVbMTozXSwgRjEuY29vcmRpbmF0ZS50aW1lWzE6M10pLCBkaWdpdHM9MykKKQoKIyBHcm91cGVkIGJhciBwbG90IGZvciBjb21wYXJpc29uIG9mIHRoZSBiZW5jaG1hcmtzCkYxLmJlbmNobWFya3MucGxvdCA8LSBnZ3Bsb3QoZGF0YT1GMS5iZW5jaG1hcmtzLmRmLCBhZXMoeD1UeXBlLCB5PVRpbWUsIGZpbGw9TWV0aG9kKSkgKwogIGdlb21fYmFyKHN0YXQ9ImlkZW50aXR5IiwgcG9zaXRpb249ImRvZGdlIikgKwogIGdlb21fdGV4dChhZXMobGFiZWw9VGltZSksIGhqdXN0PTAuNSwgY29sb3I9ImJsYWNrIiwgc2l6ZT0yLjUsIHBvc2l0aW9uID0gcG9zaXRpb25fZG9kZ2UoMC45KSwgc2l6ZT0zLjUpICsKICBzY2FsZV9maWxsX21hbnVhbCgiTWV0aG9kIiwgdmFsdWVzPWMoIkdyYWRpZW50IGRlc2NlbnQiPSIjNzBiYWNmIiwgIkNvb3JkaW5hdGUgZGVzY2VudCI9IiNlYjY5NjMiKSkgKwogICNzY2FsZV9maWxsX2JyZXdlcihwYWxldHRlPSJQYWlyZWQiKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICBnZ3RpdGxlKCJGMSAoc2l4LWh1bXAgY2FtZWwgZnVuY3Rpb24pIikgKwogIHRoZW1lKHBsb3QubWFyZ2luPXVuaXQoYygwLjUsIDAsIDAsIDApLCAiY20iKSkgKwogIGNvb3JkX2ZsaXAoKQoKIyBEYXRhZnJhbWUgcmVwcmVzZW50aW5nIHRoZSBncmFkaWVudCBhbmQgY29vcmRpbmF0ZSBkZXNjZW50IGJlbmNobWFya3Mgb24gRjIKRjIuYmVuY2htYXJrcy5kZiA8LSBkYXRhLmZyYW1lKAogIE1ldGhvZD1yZXAoYygiR3JhZGllbnQgZGVzY2VudCIsICJDb29yZGluYXRlIGRlc2NlbnQiKSwgZWFjaD0zKSwKICBUeXBlPWMoIlVzZXIiLCAiU3lzdGVtIiwgIkVsYXBzZWQgKFRvdGFsKSIpLAogIFRpbWU9cm91bmQoYyhGMi5ncmFkaWVudC50aW1lWzE6M10sIEYyLmNvb3JkaW5hdGUudGltZVsxOjNdKSwgZGlnaXRzPTMpCikKCiMgR3JvdXBlZCBiYXIgcGxvdCBmb3IgY29tcGFyaXNvbiBvZiB0aGUgYmVuY2htYXJrcwpGMi5iZW5jaG1hcmtzLnBsb3QgPC0gZ2dwbG90KGRhdGE9RjIuYmVuY2htYXJrcy5kZiwgYWVzKHg9VHlwZSwgeT1UaW1lLCBmaWxsPU1ldGhvZCkpICsKICBnZW9tX2JhcihzdGF0PSJpZGVudGl0eSIsIHBvc2l0aW9uPSJkb2RnZSIpICsKICBnZW9tX3RleHQoYWVzKGxhYmVsPVRpbWUpLCBoanVzdD0wLjUsIGNvbG9yPSJibGFjayIsIHNpemU9Mi41LCBwb3NpdGlvbiA9IHBvc2l0aW9uX2RvZGdlKDAuOSksIHNpemU9My41KSArCiAgc2NhbGVfZmlsbF9tYW51YWwoIk1ldGhvZCIsIHZhbHVlcz1jKCJHcmFkaWVudCBkZXNjZW50Ij0iIzcwYmFjZiIsICJDb29yZGluYXRlIGRlc2NlbnQiPSIjZWI2OTYzIikpICsKICAjc2NhbGVfZmlsbF9icmV3ZXIocGFsZXR0ZT0iUGFpcmVkIikgKwogIHRoZW1lX21pbmltYWwoKSArCiAgZ2d0aXRsZSgiRjIgKHBlYWtzIGZ1bmN0aW9uKSIpICsKICBjb29yZF9mbGlwKCkKCiMgQXJyYW5naW5nIHRoZSBzdWJwbG90cwpiZW5jaG1hcmtzLnBsb3QgPC0gZ2dhcnJhbmdlKEYxLmJlbmNobWFya3MucGxvdCwgRjIuYmVuY2htYXJrcy5wbG90LCBucm93PTIsIGNvbW1vbi5sZWdlbmQ9VFJVRSwgbGVnZW5kPSJib3R0b20iKQpgYGAKClBsb3R0aW5nIHRoZSBiZW5jaG1hcmtzIGNvbXBhcmlzb246CmBgYHtyfQojIEFkZCBhIHBsb3QgdGl0bGUKYW5ub3RhdGVfZmlndXJlKGJlbmNobWFya3MucGxvdCwgCiAgICAgICAgICAgICAgICB0b3A9dGV4dF9ncm9iKCJHcmFkaWVudCBhbmQgY29vcmRpbmF0ZSBkZXNjZW50IGJlbmNobWFya3MiLCBzaXplPTE2LCBmYWNlPSJib2xkIikpCmBgYAoKQXMgZXhwbGFpbmVkIGVhcmxpZXIsIGNvb3JkaW5hdGUgZGVzY2VudCB0ZW5kcyB0byBvcHRpbWl6ZSBmYXN0ZXIgKGluIHRlcm1zIG9mIHJ1bi10aW1lKSB0aGFuIGdyYWRpZW50IGRlc2NlbnQuIERlc3BpdGUgdGhpcywgd2UgY2Fubm90IGRlZmluaXRlbHkgYXNzdW1lIHRoYXQgY29vcmRpbmF0ZSBkZXNjZW50IHdpbGwgYWx3YXlzIGJlIGZhc3RlciB3aXRob3V0IHBlcmZvcm1pbmcgcmVwZWF0ZWQgZXhwZXJpbWVudHMgb3IgdHJ5aW5nIG90aGVyIGZ1bmN0aW9ucyBhbmQgY29tYmluYXRpb25zIG9mICRcZXRhJCwgJFxlcHNpbG9uJCBhbmQgc3RhcnRpbmcgcG9zaXRpb24uCgojIyBOdW1iZXIgb2YgaXRlcmF0aW9ucwoKUHJlcGFyaW5nIHRoZSBpdGVyYXRpb24gY29tcGFyaXNvbiBwbG90OgpgYGB7ciwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KIyBEYXRhZnJhbWUgcmVwcmVzZW50aW5nIHRoZSBncmFkaWVudCBhbmQgY29vcmRpbmF0ZSBkZXNjZW50IGl0ZXJhdGlvbnMgb24gRjEKRjEuaXRlcmF0aW9ucy5kZiA8LSBkYXRhLmZyYW1lKAogIE1ldGhvZD1jKCJHcmFkaWVudCBkZXNjZW50IiwgIkNvb3JkaW5hdGUgZGVzY2VudCIpLAogIEl0ZXJhdGlvbnM9cm91bmQoYXMubnVtZXJpYyhjKEYxLmdyYWRpZW50LnJlc3VsdHNbWzJdXSwgRjEuY29vcmRpbmF0ZS5pdGVyYXRpb25zKSkpCikKCiMgQmFyIHBsb3QgZm9yIGNvbXBhcmlzb24gb2YgaXRlcmF0aW9ucwpGMS5pdGVyYXRpb25zLnBsb3QgPC0gZ2dwbG90KGRhdGE9RjEuaXRlcmF0aW9ucy5kZiwgYWVzKHg9TWV0aG9kLCB5PUl0ZXJhdGlvbnMsIGZpbGw9TWV0aG9kKSkgKwogIGdlb21fYmFyKHN0YXQ9ImlkZW50aXR5IiwgcG9zaXRpb249ImRvZGdlIikgKwogIHNjYWxlX2ZpbGxfbWFudWFsKCJNZXRob2QiLCB2YWx1ZXM9YygiR3JhZGllbnQgZGVzY2VudCI9IiM3MGJhY2YiLCAiQ29vcmRpbmF0ZSBkZXNjZW50Ij0iI2ViNjk2MyIpKSArCiAgI3NjYWxlX2ZpbGxfYnJld2VyKHBhbGV0dGU9IlBhaXJlZCIpICsKICBnZW9tX3RleHQoYWVzKGxhYmVsPUl0ZXJhdGlvbnMpLCBoanVzdD0zLCBjb2xvcj0id2hpdGUiLCBzaXplPTQsIHBvc2l0aW9uID0gcG9zaXRpb25fZG9kZ2UoMC45KSwgc2l6ZT0zLjUpICsKICBzY2FsZV95X2NvbnRpbnVvdXMoYnJlYWtzPWZ1bmN0aW9uKHgpIHVuaXF1ZShmbG9vcihwcmV0dHkoc2VxKDAsIChtYXgoeCkgKyAxKSAqIDEuMSkpKSkpICsgCiAgdGhlbWVfbWluaW1hbCgpICsKICB0aGVtZShheGlzLnRleHQueSA9IGVsZW1lbnRfYmxhbmsoKSwgYXhpcy50aWNrcy55ID0gZWxlbWVudF9ibGFuaygpKSArCiAgZ2d0aXRsZSgiRjEgKHNpeC1odW1wIGNhbWVsIGZ1bmN0aW9uKSIpICsKICB0aGVtZShwbG90Lm1hcmdpbj11bml0KGMoMC41LCAwLCAwLCAwKSwgImNtIikpICsKICBjb29yZF9mbGlwKCkKCiMgRGF0YWZyYW1lIHJlcHJlc2VudGluZyB0aGUgZ3JhZGllbnQgYW5kIGNvb3JkaW5hdGUgZGVzY2VudCBpdGVyYXRpb25zIG9uIEYyCkYyLml0ZXJhdGlvbnMuZGYgPC0gZGF0YS5mcmFtZSgKICBNZXRob2Q9YygiR3JhZGllbnQgZGVzY2VudCIsICJDb29yZGluYXRlIGRlc2NlbnQiKSwKICBJdGVyYXRpb25zPXJvdW5kKGFzLm51bWVyaWMoYyhGMi5ncmFkaWVudC5yZXN1bHRzW1syXV0sIEYyLmNvb3JkaW5hdGUuaXRlcmF0aW9ucykpKQopCgojIEJhciBwbG90IGZvciBjb21wYXJpc29uIG9mIGl0ZXJhdGlvbnMKRjIuaXRlcmF0aW9ucy5wbG90IDwtIGdncGxvdChkYXRhPUYyLml0ZXJhdGlvbnMuZGYsIGFlcyh4PU1ldGhvZCwgeT1JdGVyYXRpb25zLCBmaWxsPU1ldGhvZCkpICsKICBnZW9tX2JhcihzdGF0PSJpZGVudGl0eSIsIHBvc2l0aW9uPSJkb2RnZSIpICsKICBzY2FsZV9maWxsX21hbnVhbCgiTWV0aG9kIiwgdmFsdWVzPWMoIkdyYWRpZW50IGRlc2NlbnQiPSIjNzBiYWNmIiwgIkNvb3JkaW5hdGUgZGVzY2VudCI9IiNlYjY5NjMiKSkgKwogICNzY2FsZV9maWxsX2JyZXdlcihwYWxldHRlPSJQYWlyZWQiKSArCiAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1JdGVyYXRpb25zKSwgaGp1c3Q9MywgY29sb3I9IndoaXRlIiwgc2l6ZT00LCBwb3NpdGlvbiA9IHBvc2l0aW9uX2RvZGdlKDAuOSksIHNpemU9My41KSArCiAgc2NhbGVfeV9jb250aW51b3VzKGJyZWFrcz1mdW5jdGlvbih4KSB1bmlxdWUoZmxvb3IocHJldHR5KHNlcSgwLCAobWF4KHgpICsgMSkgKiAxLjEpKSkpKSArIAogIHRoZW1lX21pbmltYWwoKSArCiAgdGhlbWUoYXhpcy50ZXh0LnkgPSBlbGVtZW50X2JsYW5rKCksIGF4aXMudGlja3MueSA9IGVsZW1lbnRfYmxhbmsoKSkgKwogIGdndGl0bGUoIkYyIChwZWFrcyBmdW5jdGlvbikiKSArCiAgY29vcmRfZmxpcCgpCgojIEFycmFuZ2luZyB0aGUgc3VicGxvdHMKaXRlcmF0aW9ucy5wbG90IDwtIGdnYXJyYW5nZShGMS5pdGVyYXRpb25zLnBsb3QsIEYyLml0ZXJhdGlvbnMucGxvdCwgbnJvdz0yLCBjb21tb24ubGVnZW5kPVRSVUUsIGxlZ2VuZD0iYm90dG9tIikKYGBgCgpQbG90dGluZyB0aGUgaXRlcmF0aW9ucyBjb21wYXJpc29uOgpgYGB7cn0KIyBBZGQgYSBwbG90IHRpdGxlCmFubm90YXRlX2ZpZ3VyZShpdGVyYXRpb25zLnBsb3QsIAogICAgICAgICAgICAgICAgdG9wPXRleHRfZ3JvYigiR3JhZGllbnQgYW5kIGNvb3JkaW5hdGUgZGVzY2VudCBpdGVyYXRpb25zIiwgc2l6ZT0xNiwgZmFjZT0iYm9sZCIpKQpgYGAKClVubGlrZSBiZW5jaG1hcmtzLCB0aGUgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgdGhhdCBlYWNoIG9mIHRoZXNlIG9wdGltaXphdGlvbiBtZXRob2QgdGFrZXMgdG8gY29udmVyZ2UgKGlmIGl0IGRvZXMgY29udmVyZ2UpIGRvZXMgbm90IHZhcnkgcGVyIGV4cGVyaW1lbnQtLS1pdCB3aWxsIG5ldmVyIGNoYW5nZSB1bmxlc3Mgd2UgY2hhbmdlICRcZXRhJCwgJFxlcHNpbG9uJCBvciB0aGUgc3RhcnRpbmcgcG9zaXRpb24sIHdoaWNoIHdlIGRpZG4ndC4gRm9yIHRoaXMgcmVhc29uLCByZXBlYXRlZCBleHBlcmltZW50cyBhcmUgbm90IGFzIG5lY2Vzc2FyeSBhcyB0aGV5IGFyZSBmb3IgYmVuY2htYXJraW5nLCB3aGVyZSB0aGUgdW5jZXJ0YWludHkgb2YgQ1BVIHJlc291cmNlIGFsbG9jYXRpb24gZXRjLiBpcyBlbm91Z2ggdG8gd2FycmFudCByZXBlYXRlZCBleHBlcmltZW50cy4gCgpIb3dldmVyLCBpdCBzdGlsbCBpc24ndCBmYWlyIHRvIG1ha2UgYSBjb25jcmV0ZSBjb25jbHVzaW9uIGZyb20gdGhlc2UgcmVzdWx0cywgc2luY2Ugd2Ugd291bGQgbmVlZCB0byB0ZXN0IHRoZSBvcHRpbWl6YXRpb24gbWV0aG9kcyBvbiBkaWZmZXJlbnQgb2JqZWN0aXZlIGZ1bmN0aW9ucywgZGlmZmVyZW50ICRcZXRhJCwgJFxlcHNpbG9uJCBhbmQgc3RhcnRpbmcgcG9zaXRpb25zLgoKTmV2ZXJ0aGVsZXNzLCBjb29yZGluYXRlIGRlc2NlbnQgb3B0aW1pemVkIHRoZSBvYmplY3RpdmUgZnVuY3Rpb25zIGluIGZhciBtb3JlIGl0ZXJhdGlvbnMgdGhhbiBncmFkaWVudCBkZXNjZW50LgoKIyBSZXNvdXJjZXMKCltebC1iZmdzXTogaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTGltaXRlZC1tZW1vcnlfQkZHUwoKW15nbG1uZXRdOiBodHRwczovL3dlYi5zdGFuZm9yZC5lZHUvfmhhc3RpZS9UQUxLUy9nbG1uZXQucGRmCgpbXmNvb3JkaW5hdGUtZGVzY2VudF06IGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0Nvb3JkaW5hdGVfZGVzY2VudAoKW15jYW1lbF06IGh0dHBzOi8vd3d3LnNmdS5jYS9+c3N1cmphbm8vY2FtZWw2Lmh0bWwKCltecGVha3NdOiBodHRwczovL2FsLXJvb21pLm9yZy9iZW5jaG1hcmtzL3VuY29uc3RyYWluZWQvMi1kaW1lbnNpb25zLzYzLXBlYWtzLWZ1bmN0aW9uCgpbXmRlcml2YXRpdmUtZnJlZV06IGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0Rlcml2YXRpdmUtZnJlZV9vcHRpbWl6YXRpb24KCltebmVsZGVyLW1lYWRdOiBodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9OZWxkZXIlRTIlODAlOTNNZWFkX21ldGhvZAoKW15wcm9jLXRpbWVdOiBodHRwczovL3N0YXQuZXRoei5jaC9SLW1hbnVhbC9SLWRldmVsL2xpYnJhcnkvYmFzZS9odG1sL3Byb2MudGltZS5odG1sCgpbXmdyYWRpZW50LWRlc2NlbnRdOiBodHRwczovL21sLWNoZWF0c2hlZXQucmVhZHRoZWRvY3MuaW8vZW4vbGF0ZXN0L2dyYWRpZW50X2Rlc2NlbnQuaHRtbA==